<style> h1 { text-align: center; } h3 { margin-bottom: 5px; color: steelblue; } #content { width: 800px; text-align: justify; padding: 20px; } #interactive { text-align: center; padding: 2px; float: right; margin-left: 30px; margin-bottom: 10px; } </style> </head> <body> <center> <div id=content> <H1> </H1> <H2>User-centric, Adaptive and Collaborative Information Filtering </H2> <p><strong>An NSF funded Collaborative Project # III-COR </strong><a href="http://www.nsf.gov/awardsearch/showAward.do?AwardNumber=0704628"><strong>0704628</strong></a><strong> & </strong><a href="http://www.nsf.gov/awardsearch/showAward.do?AwardNumber=0704689"><strong>0704689</strong></a></p> <h3>Quarterly Report: 2nd Year, 4th Quarter</h3> <H3>Title: Optimal Ordering of Prediction Tasks</H3> <br><br> <H3>Introduction</H3> <div id=interactive> <img src="interactive.png" style='border: solid 1px gray;'><br> <em>Multiple prediction tasks with user interaction.</em> </div> Much research in statistical learning has focussed on the optimization of classification, regression, recommendation, and retrieval systems in isolation. However, in many practical applications, the user needs to interact with multiple prediction systems to accomplish a higher level goal, e.g., interacting with multiple decision support systems to resolve each trouble report in a troubleshooting system, or annotating each text document with respect to multiple classification taxonomies, and so on. If the tasks are interrelated, as is often the case in such scenarios, the order in which the tasks are posed may have a significant impact on the effective propagation of user feedback through the prediction tasks, affecting their overall performance. How to find such an order for multiple prediction tasks to maximize their overall performance, and hence, minimize user annotation effort, is an interesting challenge for information retrieval and machine learning research. <br><br> A motivating example that involves heterogeneous (classification, regression, and retrieval) predictions is interactive trouble report management -- each trouble report from the customer triggers a sequence of interdependent decisions, e.g., determining the priority, category, sub-categories, hardware type, and software type, assigning an expert, and finally formulating a resolution. For making each of these decisions, the user would be assisted by the system, which makes helpful predictions for each task and receives corresponding user feedback. It might be possible to come up with an ordering of these decisions that improves the overall accuracy of the predictions through more efficient use of the user's feedback. For example, it might be beneficial to pin down the hardware and software type of the problem before assigning an expert, because historical data suggests that the latter decision depends heavily on the former. By doing so, the system would be able to make more accurate predictions for the expert assignment. How to optimize the task order by simultaneously taking into account all such relationships and dependencies leads to a hard combinatorial optimization problem. <br><br> We have developed new methods for solving the optimal task ordering problem using an approximate formulation in terms of pairwise task order preferences, reducing the problem to the well-known Linear Ordering Problem. We proposed and experimented with two approaches for finding pairwise task order preferences: <ol> <li><strong>Entropy-based approach:</strong> A classifier-agnostic approach based on conditional entropy that chooses prediction tasks whose correct labels lead to the least uncertainty for the remaining predictions. <li><strong>Classifier-based approach:</strong> A classifier-dependent approach that empirically determines which task orders are favored by the classifier for better predictive performance. This is a flexible approach that allows task order optimization for different target performance metrics. We experiment with five different performance measures (see Tables 1 and 2). </ol> <H3>Experiments</H3> We applied the proposed solutions to two practical applications: <ol> <li><strong>The Accenture dataset</strong>, that contains 60,000 documents related to client projects. The documents need to be categorized into multiple inter-related taxonomies, which correspond to the multiple prediction tasks. <li><strong>The F/A-18 dataset</strong>, that contains 6,000 aircraft trouble reports. The prediction tasks comprise of multiple categorizations, engineer assignments, priority assignment for each trouble report. </ol> Our experiments show encouraging improvements in predictive performance when the proposed task ordering approaches are used, as compared to the baseline approach of using un-optimized task orders. <H3>Results</H3> Figure 1 shows a summary of the performance obtained by various approaches on the Accenture dataset. Tables 1 and 2 report detailed results obtained by each method for different combinations of optimization costs and target evaluation metrics.<br><br> <B>Figure 1.</B> <em>Summary of the results on the Accenture dataset.</em><br> <img src="summary.png"> <br><br> <B>Table 1.</B> <em>Accenture dataset -- Performance (columns) of various task ordering approaches (rows). In four of the five applicable cases, the best performance (bold entry in each column) is obtained when the performance and task order optimization criterion are matched.</em><BR> <img src="accenture.png"><br> <br><br><br> <B>Table 2.</B> <em>F/A-18 dataset -- Performance (columns) of various task ordering approaches (rows). In all of the five applicable cases, the best performance (bold entry in each column) is obtained when the performance and task order optimization criterion are matched.</em><br> <img src="fa18.png"> <br> </div> </body> </html>