Abstract

In this paper, we propose exact passive-aggressive (PA) online algorithms for learning to rank. The proposed algorithms can be used even when we have interval labels instead of actual labels for examples. The proposed algorithms solve a convex optimization problem at every trial. We find exact solution to those optimization problems to determine the updated parameters. We propose support class algorithm (SCA) which finds the active constraints using the KKT conditions of the optimization problems. These active constrains form support set which determines the set of thresholds that need to be updated. We derive update rules for PA, PA-I and PA-II. We show that the proposed algorithms maintain the ordering of the thresholds after every trial. We provide the mistake bounds of the proposed algorithms in both ideal and general settings. We also show experimentally that the proposed algorithms successfully learn accurate classifiers using interval labels as well as exact labels. Proposed algorithms also do well compared to other approaches.

Abstract

fMRI semantic category understanding using linguistic encoding models attempt to learn a forward mapping that relates stimuli to the corresponding brain activation. Classical encoding models use linear multi-variate methods to predict the brain activation (all voxels) given the stimulus. However, these methods essentially assume multiple regions as one large uniform region or several independent regions, ignoring connections among them. In this paper, we present a mixture of expertsbased model where a group of experts captures brain activity patterns related to particular regions of interest (ROI) and also show the discrimination across different experts. The model is trained word stimuli encoded as 25-dimensional feature vectors as input and the corresponding brain responses as output. Given a new word (25-dimensional feature vector), it predicts the entire brain activation as the linear combination of multiple experts’ brain activations. We argue that each expert learns a certain region of brain activations corresponding to its category of words, which solves the problem of identifying the regions with a simple encoding model. We showcase that proposed mixture of experts-based model indeed learns region-based experts to predict the brain activations with high spatial accuracy.

Abstract

Decentralized (PO) MDPs provide a rigorous framework for sequential multiagent decision making under uncertainty. However, their high computational complexity limits the practical impact. To address scalability and real-world impact, we focus on settings where a large number of agents primarily interact through complex joint-rewards that depend on their entire histories of states and actions. Such history-based rewards encapsulate the notion of events or tasks such that the team reward is given only when the joint-task is completed. Algorithmically, we contribute---1) A nonlinear programming (NLP) formulation for such event-based planning model; 2) A probabilistic inference based approach that scales much better than NLP solvers for a large number of agents; 3) A policy gradient based multiagent reinforcement learning approach that scales well even for exponential state-spaces. Our inference and RL-based advances enable us to solve a large real-world multiagent coverage problem modeling schedule coordination of agents in a real urban subway network where other approaches fail to scale.

Abstract

Traffic management during emergency evacuation throws up a different set of challenges than a regular traffic management. We focus here on one particular challenge, namely prioritized routing. Prioritized routing may need to happen even during normal times but stands out during emergencies, since emergency vehicles, police vehicles and vehicles (such as buses) that carry a lot more people may need to have a higher priority in terms of evacuation. It is also reasonable to assume that traffic police may need to perform a centralized control of traffic since they typically have a global view of the emergency and possibly have accurate real-time updates. We therefore make the following contributions in this paper: (a) We map the prioritized routing problem to the minimum-cost maximum-flow problem, a standard problem formulation in network flow theory. (b) We then develop the Prioritized Routing Assistant for Flow …

Abstract

Handwriting recognition (HWR) in Indicscripts, like Devanagari is very challenging due to thesubtleties in the scripts, variations in rendering and the cur-sive nature of the handwriting. Lack of public handwritingdatasets in Indic scripts has long stymied the development ofoffline handwritten word recognizers and made comparisonacross different methods a tedious task in the field. Inthis paper, we release a new handwritten word dataset forDevanagari, IIIT-HW-Dev to alleviate some of these issues.We benchmark the IIIT-HW-Dev dataset using a CNN-RNN hybrid architecture. Furthermore, using this architec-ture, we empirically show that usage of synthetic data andcross lingual transfer learning helps alleviate the issue of lackof training data. We use this proposed pipeline on a publicdataset, RoyDB and achieve state of the art results.

Abstract

Discrete labeling problems are often solvedby formulating them as an integer program,and relaxing the integrality constraint to acontinuous domain. While the continuous re-laxation is closely related to the original in-teger program, its optimal solution is oftenfractional. Thus, the success of a relaxationdepends crucially on the availability of an ac-curate rounding procedure. The problem ofidentifying an accurate rounding procedurehas mainly been tackled in the theoreticalcomputer science community through math-ematical analysis of the worst-case. However,this approach is both onerous and ignores thedistribution of the data encountered in prac-tice. We present a novel interpretation ofrounding procedures as sampling from a la-tent variable model, which opens the door tothe use of powerful machine learning formu-lations in their design. Inspired by the recentsuccess of deep latent variable models we pa-rameterize rounding procedures as a neuralnetwork, which lends itself to efficient opti-mization via back-propagation. By minimiz-ing the expected value of the objective of thediscrete labeling problem over training sam-ples, we learn a rounding procedure that ismore suited to the task at hand. Using bothsynthetic and real world data sets, we demon-strate that our approach can outperform thestate-of-the-art hand-designed rounding pro-cedures

Abstract

Our goal is to spot words in silent speech videos withoutexplicitly recognizing the spoken words, where the lip mo-tion of the speaker is clearly visible and audio is absent. Ex-isting work in this domain has mainly focused on recogniz-ing a fixed set of words in word-segmented lip videos, whichlimits the applicability of the learned model due to limitedvocabulary and high dependency on the model’s recogni-tion performance.Our contribution is two-fold: 1) we develop a pipelinefor recognition-free retrieval, and show its performanceagainst recognition-based retrieval on a large-scale datasetand another set of out-of-vocabulary words. 2) We intro-duce a query expansion technique using pseudo-relevantfeedback and propose a novel re-ranking method based onmaximizing the correlation between spatio-temporal land-marks of the query and the top retrieval candidates. Ourword spotting method achieves 35% higher mean aver-age precision over recognition-based method on large-scaleLRW dataset. Finally, we demonstrate the application of themethod by word spotting in a popular speech video (“Thegreat dictator” by Charlie Chaplin) where we show that theword retrieval can be used to understand what was spokenperhaps in the silent movies

Abstract

The accuracy of information retrieval systems is often measured using complex loss functions such as the average precision (AP) or the normalized discounted cumulative gain (NDCG). Given a set of positive and negative samples, the parameters of a retrieval system can be estimated by minimizing these loss functions. However, the non-differentiability and non-decomposability of these loss functions does not allow for simple gradient based optimization algorithms. This issue is generally circumvented by either optimizing a structured hinge-loss upper bound to the loss function or by using asymptotic methods like the direct-loss minimization framework. Yet, the high computational complexity of loss-augmented inference, which is necessary for both the frameworks, prohibits its use in large training data sets. To alleviate this deficiency, we present a novel quicksort flavored algorithm for a large class of non-decomposable loss functions. We provide a complete characterization of the loss functions that are amenable to our algorithm, and show that it includes both AP and NDCG based loss functions. Furthermore, we prove that no comparison based algorithm can improve upon the computational complexity of our approach asymptotically. We demonstrate the effectiveness of our approach in the context of optimizing the structured hinge loss upper bound of AP and NDCG loss for learning models for a variety of vision tasks. We show that our approach provides significantly better results than simpler decomposable loss functions, while requiring a comparable training time.

Abstract

With the increase in the number of students enrolled in the university system, regular assessment of student performance has become challenging. This is specially true in case of summative assessments, where one expects the student to write down an answer on paper, rather than selecting a correct answer from multiple choices. In this paper, we present a document image workflow system that helps in scaling the handwritten student assessments in a typical university setting. We argue that this improves the efficiency since the book keeping time as well as physical paper movement is minimized. An electronic workflow can make the anonymization easy, alleviating the fear of biases in many cases. Also, parallel and distributed assessment by multiple instructors is straightforward in an electronic workflow system. At the heart of our solution, we have (i) a distributed image capture module with a mobile phone (ii) image processing algorithms that improve the quality and readability (iii) image annotation module that process the evaluations/feedbacks as a separate layer. Our system also acts as a platform for modern image analysis which can be adapted to the domain of student assessments. This include (i) Handwriting recognition and word spotting [5] (ii) Measure of document similarity [6] (iii) Aesthetic analysis of handwriting [7] (iv) Identity of the writer [4] etc. With the handwriting assessment workflow system, all these recent advances in computer vision can become practical and applicable in evaluating student assessments

Abstract

Deep CNNs for semantic segmentation have high memory and run time requirements. Various approaches have been proposed to make CNNs efficient like grouped, shuffled, depth-wise separable convolutions. We study the effectiveness of these techniques on a real-time semantic segmentation architecture like ERFNet for improving runtime by over 5X. We apply these techniques to CNN layers partially or fully and evaluate the testing accuracies on Cityscapes dataset. We obtain accuracy vs parameters/FLOPs trade offs, giving accuracy scores for models that can run under specified runtime budgets. We further propose a novel training procedure which starts out with a dense convolution but gradually evolves towards a grouped convolution. We show that our proposed training method and efficient architecture design can improve accuracies by over 8% with depthwise separable convolutions applied on the encoder of ERFNet and attaching a light weight decoder. This results in a model which has a 5X improvement in FLOPs while only suffering a 4% degradation in accuracy with respect to ERFNet.