SEQUENTIAL DECISION MAKING FOR ACTIVE LEARNING AND INFERENCE IN ONLINE SETTINGS

124 pagesThis dissertation focuses on sequential decision making for active learning and inference in online settings. In particular, we consider the settings where the hypothesis space is large and labeled data are expensive. Examples include unusual activities in surveillance feedings, target search among large areas, frauds in financial transactions, attacks and intrusions in communication and computer networks, anomalies in infrastructures such as bridges, buildings, and the power grid that may indicate catastrophes. All those applications above are involved with two challenges: (1) massive search space leads to high detection delay (2) labeled data are expensive and time consuming. For active inference, the objective is to detect such event as soon as possible, with a constraint on either the detection accuracy. For active learning, the goal is to minimize the label complexity with certain requirement on the cumulative classification error. The key solution to both problems is to utilize active learning approaches that actively choose which samples to be labeled based on the past observations. In active approaches, the decision maker exert control on which data points to learn from with the objective of label efficiency In this dissertation, we first focus on designing active learning algorithms for active inference. We consider an anomaly detection problem among heterogeneous processes. At each time, a subset of processes can be probed. The objective is to design a sequential probing strategy that dynamically determines which processes to observe at each time and when to terminate the search so that the expected detection time is minimized under a constraint on the probability of misclassifying any process. A low-complexity deterministic test is shown to enjoy the same asymptotic optimality while offering significantly better performance in the finite regime and faster convergence to the optimal rate function, especially when the number of processes is large. Furthermore, the proposed test offers considerable reduction in implementation complexity. Then, we consider active learning algorithms for classifying streaming instances within the framework of statistical learning theory in online settings. At each time, the learner decides whether to query the label of the current instance. If the decision is to not query, the learner predicts the label and receives no feedback on the correctness of the prediction. The objective is to minimize the number of queries while constraining the number of prediction errors over a horizon of length $T$. The proposed algorithm is shown to outperform existing online active learning algorithms as well as extensions of representative offline algorithms developed under the PAC setting