Shailesh Kumar

Distributed representations of words and paragraphs as semantic embeddings in high dimensional data are used across a number of Natural Language Understanding tasks such as retrieval, translation, and classification. In this work, we propose "Class Vectors" - a framework for learning a vector per class in the same embedding space as the word and paragraph embeddings. Similarity between these class vectors and word vectors are used as features to classify a document to a class. In experiment on… Show more

Distributed representations of words and paragraphs as semantic embeddings in high dimensional data are used across a number of Natural Language Understanding tasks such as retrieval, translation, and classification. In this work, we propose "Class Vectors" - a framework for learning a vector per class in the same embedding space as the word and paragraph embeddings. Similarity between these class vectors and word vectors are used as features to classify a document to a class. In experiment on several sentiment analysis tasks such as Yelp reviews and Amazon electronic product reviews, class vectors have shown better or comparable results in classification while learning very meaningful class embeddings. Show less

Detecting compact overlapping communities in large networks is an important pattern recognition problem with applications in many domains. Most community detection algorithms trade-off between community sizes, their compactness and the scalability of finding communities.
Clique Percolation Method (CPM) and Local Fitness Maximization (LFM) are two prominent and commonly used overlapping community detection methods that scale with large networks. However, significant number of communities… Show more

Detecting compact overlapping communities in large networks is an important pattern recognition problem with applications in many domains. Most community detection algorithms trade-off between community sizes, their compactness and the scalability of finding communities.
Clique Percolation Method (CPM) and Local Fitness Maximization (LFM) are two prominent and commonly used overlapping community detection methods that scale with large networks. However, significant number of communities found by them are large, noisy, and loose. In this paper, we propose a general algorithm that takes such large and loose communities generated by any method and refines them into compact communities in a systematic fashion. We define a new measure of community-ness based on eigenvector centrality, identify loose communities using this measure and propose an algorithm for partitioning such loose communities into compact communities. We refine the communities found by CPM and LFM using our method and show their effectiveness compared to the original communities in a recommendation engine task.
Show less

Labels associated with social images are valuable source of information for tasks of image annotation, understanding and retrieval. These labels are often found to be noisy, mainly due to the collaborative tagging activities of users. Existing methods on annotation have been developed and verified on noise free labels of images. In this paper, we propose a novel and generic framework that exploits the collective knowledge embedded in noisy label co-occurrence pairs to derive robust annotations.… Show more

Labels associated with social images are valuable source of information for tasks of image annotation, understanding and retrieval. These labels are often found to be noisy, mainly due to the collaborative tagging activities of users. Existing methods on annotation have been developed and verified on noise free labels of images. In this paper, we propose a novel and generic framework that exploits the collective knowledge embedded in noisy label co-occurrence pairs to derive robust annotations. We compare our method with a well-known image annotation algorithm and show its superiority in terms of annotation accuracy on benchmark Corel5K and ESP datasets in presence of noisy labels. Show less

Understanding the nature of data is the key to building good representations. In domains such as natural images, the data comes from very complex distributions which are hard to capture. Feature learning intends to discover or best approximate these underlying distributions and use their knowledge to weed out irrelevant information, preserving most of the relevant information. Feature learning can thus be seen as a form of dimensionality reduction. In this paper, we describe a feature learning… Show more

Understanding the nature of data is the key to building good representations. In domains such as natural images, the data comes from very complex distributions which are hard to capture. Feature learning intends to discover or best approximate these underlying distributions and use their knowledge to weed out irrelevant information, preserving most of the relevant information. Feature learning can thus be seen as a form of dimensionality reduction. In this paper, we describe a feature learning scheme for natural images. We hypothesize that image patches do not all come from the same distribution, they lie in multiple nonlinear subspaces. We propose a framework that uses K-Restricted Boltzmann Machines (K-RBMS) to learn multiple non-linear subspaces in the raw image space. Projections of the image patches into these subspaces gives us features, which we use to build image representations. Our algorithm solves the coupled problem of finding the right non-linear subspaces in the input space and associating image patches with those subspaces in an iterative EM like algorithm to minimize the overall reconstruction error. Extensive empirical results over several popular image classification datasets show that representations based on our framework outperform the traditional feature representations such as the SIFT based Bag-of-Words (BoW) and convolutional deep belief networks. Show less

Frequent Itemset Mining (FISM) attempts to find large and frequent itemsets in bag-of-items data such as retail market baskets. Such data has two properties that are not naturally addressed by FISM: (i) a market basket might contain items from more than one customer intent (mixture property) and (ii) only a subset of items related to a customer intent are present in most market baskets (projection property). We propose a simple and robust framework called LOGICAL ITEMSET MINING (LISM) that… Show more

Frequent Itemset Mining (FISM) attempts to find large and frequent itemsets in bag-of-items data such as retail market baskets. Such data has two properties that are not naturally addressed by FISM: (i) a market basket might contain items from more than one customer intent (mixture property) and (ii) only a subset of items related to a customer intent are present in most market baskets (projection property). We propose a simple and robust framework called LOGICAL ITEMSET MINING (LISM) that treats each market basket as a mixture-of, projections-of, latent customer intents. LISM attempts to discover logical itemsets from such bagof-items data. Each logical itemset can be interpreted as a latent customer intent in retail or semantic concept in text tagsets. While the mixture and projection properties are easy to appreciate in retail domain, they are present in almost all types of bag-of-items data. Through experiments on two large datasets, we demonstrate the quality, novelty, and actionability of logical itemsets discovered by the simple, scalable, and aggressively noise-robust LISM framework. We conclude that while FISM discovers a large number of noisy, observed, and
frequent itemsets, LISM discovers a small number of high quality, latent logical itemsets. Show less

Image analysis tasks such as classi?cation, clustering, detection, and retrieval are only as good as the feature representation of the images they use. Much research in computer vision is focused on fi?nding better or semantically richer image representations. Bag of visual Words (BoW) is a representation that has emerged as an e?ffective one for a variety of computer vision tasks. BoW methods traditionally use low level features. We have devised a strategy to use these low level features to… Show more

Image analysis tasks such as classi?cation, clustering, detection, and retrieval are only as good as the feature representation of the images they use. Much research in computer vision is focused on fi?nding better or semantically richer image representations. Bag of visual Words (BoW) is a representation that has emerged as an e?ffective one for a variety of computer vision tasks. BoW methods traditionally use low level features. We have devised a strategy to use these low level features to create \higher level" features by making use of the spatial context in images. In this paper, we propose a novel hierarchical feature learning framework that uses a Naive Bayes Clustering algorithm to convert a 2-D symbolic image at one level to a 2-D symbolic image at the next level with richer features. On two popular datasets, Pascal VOC 2007 and Caltech 101, we empirically show that classi?cation accuracy ob-
tained from the hierarchical features computed using our approach is signi?cantly higher than the traditional SIFT based BoW representation of images even though our image representations are more compact. Show less

Many classification problems involve high dimensional inputs and a large number of classes. Multiclassifier fusion approaches to such difficult problems typically centre around smart feature extraction, input resampling methods, or input space partitioning to exploit modular learning. In this paper, we investigate how partitioning of the output space (i.e. the set of class labels) can be exploited in a multiclassifier fusion framework to simplify such problems and to yield better solutions… Show more

Many classification problems involve high dimensional inputs and a large number of classes. Multiclassifier fusion approaches to such difficult problems typically centre around smart feature extraction, input resampling methods, or input space partitioning to exploit modular learning. In this paper, we investigate how partitioning of the output space (i.e. the set of class labels) can be exploited in a multiclassifier fusion framework to simplify such problems and to yield better solutions. Specifically, we introduce a hierarchical technique to recursively decompose a C-class problem into C_1 two-(meta) class problems. A generalised modular learning framework is used to partition a set of classes into two disjoint groups called meta-classes. The coupled problems of finding a good partition and of searching for a linear feature extractor that best discriminates the resulting two meta-classes are solved simultaneously at each stage of the recursive algorithm. This results in a binary tree whose leaf nodes represent the original C classes. The proposed hierarchical multiclassifier framework is particularly effective for difficult classification problems involving a moderately large number of classes. The proposed method is illustrated on a problem related to classification of landcover using hyperspectral data: a 12-class AVIRIS subset with 180 bands. For this problem, the classification accuracies obtained were superior to most other techniques developed for hyperspectral classification. Moreover, the class hierarchies that were automatically discovered conformed very well with human domain experts’ opinions, which demonstrates the potential of using such a modular learning approach for discovering domain knowledge automatically from data. Show less

Wavelet based data compression methods have demonstrated superior performance over the conventional interpolative methods. However, the wavelet based methods need thresholding on the wavelet domain coefficients. Since wavelet coefficients are not commonly intuitive to engineers, significant a priori knowledge of either the wavelet coefficients or process thresholds is required. So unless thresholds are pre-specified, this requirement makes wavelets unsuitable for on-line implementations… Show more

Wavelet based data compression methods have demonstrated superior performance over the conventional interpolative methods. However, the wavelet based methods need thresholding on the wavelet domain coefficients. Since wavelet coefficients are not commonly intuitive to engineers, significant a priori knowledge of either the wavelet coefficients or process thresholds is required. So unless thresholds are pre-specified, this requirement makes wavelets unsuitable for on-line implementations. Furthermore, as the relation between the wavelet domain coefficients and the measures of the quality of compression [root mean square error (RMSE) and local point error (LPE)] is not straightforward, it is difficult to achieve good control over the quality of compression by specifying thresholds on the wavelet coefficients. In this paper, an error based criterion is proposed for online wavelet data compression. It uses semantically straightforward measures of the quality of the result to be obtained to adaptively calculate the thresholds. Given a bound on time domain error limits like the RMSE and LPE, this technique adaptively computes the threshold values in wavelet domain. Experiments show that the resulting algorithm gives superior compression as compared to other wavelet based methods. Most importantly, it can be used on-line and provides an effective way of controlling LPE and RMSE. Finally, this method can easily be extended to other on-line wavelet applications such as data rectification and de-noising. Show less

Due to advances in sensor technology, it is now possible to acquire hyperspectral data simultaneously in hundreds of bands. Algorithms that both reduce the dimensionality of the data sets and handle highly correlated bands are required to exploit the information in these data sets effectively. the authors propose a set of best-bases feature extraction algorithms that are simple, fast, and highly effective for classification of hyperspectral data. These techniques intelligently combine subsets… Show more

Due to advances in sensor technology, it is now possible to acquire hyperspectral data simultaneously in hundreds of bands. Algorithms that both reduce the dimensionality of the data sets and handle highly correlated bands are required to exploit the information in these data sets effectively. the authors propose a set of best-bases feature extraction algorithms that are simple, fast, and highly effective for classification of hyperspectral data. These techniques intelligently combine subsets of adjacent bands into a smaller number of features. Both top-down and bottom-up algorithms are proposed. The top-down algorithm recursively partitions the bands into two (not necessarily equal) sets of bands and then replaces each final set of bands by its mean value. The bottom-up algorithm builds an agglomerative tree by merging highly correlated adjacent bands and projecting them onto their Fisher direction, yielding high discrimination among classes. Both these algorithms are used in a pairwise classifier framework where the original C-class problem is divided into a set of (2C) two-class problems. The new algorithms (1) find variable length bases localized in wavelength, (2) favor grouping highly correlated adjacent bands that, when merged either by taking their mean or Fisher linear projection, yield maximum discrimination, and (3) seek orthogonal bases for each of the (2C) two-class problems into which a C-class problem can be decomposed. Experiments on an AVIRIS data set for a 12-class problem show significant improvements in classification accuracies while using a much smaller number of features Show less

We develop a Bayesian Pairwise Classifier framework that is suitable for pattern recognition problems involving a moderately large number of classes, and apply it to two character recognition datasets. A C class pattern recognition problem (e.g.; C = 26 for recognition of English Alphabet) is divided into a set of (2C) two-class problems. For each pair of classes, a Bayesian classifier based on a mixture of Gaussians (MOG) is used to model the probability density functions conditioned on a… Show more

We develop a Bayesian Pairwise Classifier framework that is suitable for pattern recognition problems involving a moderately large number of classes, and apply it to two character recognition datasets. A C class pattern recognition problem (e.g.; C = 26 for recognition of English Alphabet) is divided into a set of (2C) two-class problems. For each pair of classes, a Bayesian classifier based on a mixture of Gaussians (MOG) is used to model the probability density functions conditioned on a single feature. A forward feature selection algorithm is then used to grow the feature space, and an efficient technique is developed to obtain a MOG in the larger feature space from the MOG's in the smaller spaces. Apart from improvements in classification accuracy, the proposed architecture also provides valuable domain knowledge such as identifying what features are most important in separating a pair of characters, relative distance between any two characters, etc. Show less

Many real world classification problems involve high dimensional inputs and a large number of classes. Feature extraction and modular learning approaches can be used to simplify such problems. In this paper, we introduce a hierarchical multiclassifier paradigm in which a C- class problem is recursively decomposed into C- 1 two-class problems. A generalized modular learning framework is used to partition a set of classes into two disjoint groups called meta-classes. The coupled problem of… Show more

Many real world classification problems involve high dimensional inputs and a large number of classes. Feature extraction and modular learning approaches can be used to simplify such problems. In this paper, we introduce a hierarchical multiclassifier paradigm in which a C- class problem is recursively decomposed into C- 1 two-class problems. A generalized modular learning framework is used to partition a set of classes into two disjoint groups called meta-classes. The coupled problem of finding a good partition and of searching for a linear feature extractor that best discriminates the resulting two meta-classes are solved simultaneously at each stage of the recursive algorithm. This results in a binary tree whose leaf nodes represent the original C classes. The proposed hierarchical multiclassifier architecture was used to classify 12 types of landcover from 183-dimensional hyperspectral data. The classification accuracy was significantly improved by 4 to 10% relative to other feature extraction and modular learning approaches. Moreover, the class hierarchy that was automatically discovered conformed very well with a human domain expert–s opinion, which demonstrates the potential of such a modular learning approach for discovering domain knowledge automatically from data. Show less

Wavelet representation of a signal is efficient for process data compression. An on-line compression algorithm based on Haar wavelets is proposed here. As a new data point arrives, the algorithm computes all the approximation coefficients and updates the multiresolution tree before it prepares to receive the next data point. An efficient bookkeeping and indexing scheme improves compression ratio more significantly than batch-mode wavelet compression. Reconstruction algorithms and historian… Show more

Wavelet representation of a signal is efficient for process data compression. An on-line compression algorithm based on Haar wavelets is proposed here. As a new data point arrives, the algorithm computes all the approximation coefficients and updates the multiresolution tree before it prepares to receive the next data point. An efficient bookkeeping and indexing scheme improves compression ratio more significantly than batch-mode wavelet compression. Reconstruction algorithms and historian format for this bookkeeping are developed. Various analytical results on the bounds on compression ratio and sum of the square error that can be achieved using this algorithm are derived. Experimental evaluation over two sets of plant data shows that wavelet compression is superior to conventional interpolative methods (such as boxcar, backward slope, and SLIM3) in terms of quality of compression measured both in time and frequency domain and that the proposed on-line wavelet compression algorithm performs better than the batch-mode wavelet compression algorithm due to the efficient indexing and bookkeeping scheme. The on-line algorithm combines the high quality of compression of wavelet-based methods and on-line implementation of interpolative compression algorithms at the same time. Show less

AIRSAR and TOPSAR data were acquired over the wetlands of Bolivar Peninsula along the Gulf coast of Texas for mapping land cover types and topographic features such as beach ridges, dunes, and relict storm features. Classification of land cover over this wetlands and uplands environment is difficult because of the similarity of spectral signatures of the vegetation types. In addition, because the distribution of vegetation communities in coastal marshes is strongly related to salinity, which in… Show more

AIRSAR and TOPSAR data were acquired over the wetlands of Bolivar Peninsula along the Gulf coast of Texas for mapping land cover types and topographic features such as beach ridges, dunes, and relict storm features. Classification of land cover over this wetlands and uplands environment is difficult because of the similarity of spectral signatures of the vegetation types. In addition, because the distribution of vegetation communities in coastal marshes is strongly related to salinity, which in turn is largely dictated by frequency and duration of inundation, surface topography is critical to determination of the vegetation characteristics at any location. The potential advantages of multisensor classification, including, in particular, topographic information from a TOPSAR DEM are investigated. An approach which employs a class dependent feature selection procedure in conjunction with pairwise Bayesian classifiers is proposed and applied to the polarimetric and interferometric SAR data Show less

Conventional methods for feature selection use some kind of separability criteria or classification accuracy for computing the relevance of a feature subset to the classification task. In two-class problems, this approach may be suitable, but for problems such as character recognition with 26 classes, these feature selection algorithms are often faced with complex tradeoffs among efficacy of features for separating different subsets of classes. We propose a class-pair based feature selection… Show more

Conventional methods for feature selection use some kind of separability criteria or classification accuracy for computing the relevance of a feature subset to the classification task. In two-class problems, this approach may be suitable, but for problems such as character recognition with 26 classes, these feature selection algorithms are often faced with complex tradeoffs among efficacy of features for separating different subsets of classes. We propose a class-pair based feature selection algorithm which, in conjunction with mixture modeling technique, provides significantly superior results for differentiating a large number of classes, even when the class priors vary considerably. This technique is applied to multisensor NASA/JPL remote sensing AIRSAR data for characterizing 11 types of land cover. The proposed polychotomous approach not only gives improved test accuracy, but also reduces the number of features used. Important domain information can be derived from the features selected for different class pairs and the distance measure between these class pairs
Show less

This paper describes and evaluates the Confidence-based Dual Reinforcement Q-Routing algorithm (CDRQ-Routing) for adaptive packet routing in communication networks. CDRQ-Routing is based on an application of the Q-learning framework to network routing, as first proposed by Littman and Boyan (1993). The main contribution of CDRQ-routing is an increased quantity and an improved quality of exploration. Compared to Q-Routing, the state-of-the-art adaptive Bellman-Ford Routing algorithm, and the… Show more

This paper describes and evaluates the Confidence-based Dual Reinforcement Q-Routing algorithm (CDRQ-Routing) for adaptive packet routing in communication networks. CDRQ-Routing is based on an application of the Q-learning framework to network routing, as first proposed by Littman and Boyan (1993). The main contribution of CDRQ-routing is an increased quantity and an improved quality of exploration. Compared to Q-Routing, the state-of-the-art adaptive Bellman-Ford Routing algorithm, and the non-adaptive shortest path method, CDRQ-Routing learns superior policies significantly faster. Moreover, the overhead due to exploration is shown to be insignificant compared to the improvements achieved, which makes CDRQ-Routing a practical method for real communication networks. Show less

This paper describes and evaluates how confidence values can be used to improve the quality of exploration in Q-Routing for adaptive packet routing in communication networks. In Q-Routing each node in the network has a routing decision maker that adapts, on-line, to learn routing policies that can sustain high network loads and have low average packet delivery time. These decision makers maintain their view of the network in terms of Q values which are updated as the routing takes place. In… Show more

This paper describes and evaluates how confidence values can be used to improve the quality of exploration in Q-Routing for adaptive packet routing in communication networks. In Q-Routing each node in the network has a routing decision maker that adapts, on-line, to learn routing policies that can sustain high network loads and have low average packet delivery time. These decision makers maintain their view of the network in terms of Q values which are updated as the routing takes place. In Confidence based Q-Routing (CQ-Routing), the improved implementation of Q-Routing with confidence values, each Q value is attached with a confidence (C value) which is a measure of how closely the corresponding Q value represents the current state of the network. While the learning rate in Q-Routing is a constant, the learning rate in CQ-Routing is computed as a function of confidence values of the old and estimated Q values for each update. If either the old Q value has a low confidence or the estimated Q value has a high confidence, the learning rate is high. The quality of exploration is improved in CQ-Routing as a result of this variable learning rate. Experiments over several network topologies have shown that at low and medium loads, CQ-Routing learns the adequate routing policies significantly faster than Q-Routing, and at high loads, it learns routing policies that are significantly better than those learned by Q-Routing in terms of average packet delivery time. CQ-Routing is able to sustain higher network loads than Q-Routing, non-adaptive shortest-path routing and adaptive Bellman-Ford Routing. Finally, CQ-Routing was found to adapt significantly faster than Q-Routing to changes in network topology. Show less

Several researchers have demonstrated how neural networks can be trained to compensate for nonlinear signal distortion in e.g. digital satellite communications systems. These networks, however, require that both the original signal and its distorted version are known. Therefore, they have to be trained off-line, and they cannot adapt to changing channel characteristics. In this paper, a novel dual reinforcement learning approach is proposed that can adapt on-line while the system is performing.… Show more

Several researchers have demonstrated how neural networks can be trained to compensate for nonlinear signal distortion in e.g. digital satellite communications systems. These networks, however, require that both the original signal and its distorted version are known. Therefore, they have to be trained off-line, and they cannot adapt to changing channel characteristics. In this paper, a novel dual reinforcement learning approach is proposed that can adapt on-line while the system is performing. Assuming that the channel characteristics are the same in both directions, two predistorters at each end of the communication channel co-adapt using the output of the other predistorter to determine their own reinforcement. Using the common Volterra Series model to simulate the channel, the system is shown to successfully learn to compensate for distortions up to 30%, which is significantly higher than what might be expected in an actual channel. Show less