Scalable non-linear Support Vector Machine using hierarchical clustering

This paper discusses a method for scaling SVM with Gaussian kernel function to handle large data sets by using a selective sampling strategy for the training set. It employs a scalable hierarchical clustering algorithm to construct cluster indexing structures of the training data in the kernel induced feature space. These are then used for selective sampling of the training data for SVM to impart scalability to the training process. Empirical studies made on real world data sets show that the proposed strategy performs well on large data sets.

An improved representation of vehicle incompatibility in frontal NCAP tests using a modified rigid barrier

With the objective of better understanding the significance of New Car Assessment Program (NCAP) tests conducted by the National Highway Traffic Safety Administration (NHTSA), head-on collisions between two identical cars of different sizes and between cars and a pickup truck are studied in the present paper using LS-DYNA models. Available finite element models of a compact car (Dodge Neon), midsize car (Dodge Intrepid), and pickup truck (Chevrolet C1500) are first improved and validated by comparing theanalysis-based vehicle deceleration pulses against corresponding NCAP crash test histories reported by NHTSA. In confirmation of prevalent perception, simulation-bascd results indicate that an NCAP test against a rigid barrier is a good representation of a collision between two similar cars approaching each other at a speed of 56.3 kmph (35 mph) both in terms of peak deceleration and intrusions. However, analyses carried out for collisions between two incompatible vehicles, such as an Intrepid or Neon against a C1500, point to the inability of the NCAP tests in representing the substantially higher intrusions in the front upper regions experienced by the cars, although peak decelerations in cars arc comparable to those observed in NCAP tests. In an attempt to improve the capability of a front NCAP test to better represent real-world crashes between incompatible vehicles, i.e., ones with contrasting ride height and lower body stiffness, two modified rigid barriers are studied. One of these barriers, which is of stepped geometry with a curved front face, leads to significantly improved correlation of intrusions in the upper regions of cars with respect to those yielded in the simulation of collisions between incompatible vehicles, together with the yielding of similar vehicle peak decelerations obtained in NCAP tests.

On Finding the Natural Number of Topics with Latent Dirichlet Allocation: Some Observations

It is important to identify the ``correct'' number of topics in mechanisms like Latent Dirichlet Allocation(LDA) as they determine the quality of features that are presented as features for classifiers like SVM. In this work we propose a measure to identify the correct number of topics and offer empirical evidence in its favor in terms of classification accuracy and the number of topics that are naturally present in the corpus. We show the merit of the measure by applying it on real-world as well as synthetic data sets(both text and images). In proposing this measure, we view LDA as a matrix factorization mechanism, wherein a given corpus C is split into two matrix factors M-1 and M-2 as given by C-d*w = M1(d*t) x Q(t*w).Where d is the number of documents present in the corpus anti w is the size of the vocabulary. The quality of the split depends on ``t'', the right number of topics chosen. The measure is computed in terms of symmetric KL-Divergence of salient distributions that are derived from these matrix factors. We observe that the divergence values are higher for non-optimal number of topics - this is shown by a `dip' at the right value for `t'.

Semi-Supervised Classification Using Sparse Gaussian Process Regression

Gaussian Processes (GPs) are promising Bayesian methods for classification and regression problems. They have also been used for semi-supervised learning tasks. In this paper, we propose a new algorithm for solving semi-supervised binary classification problem using sparse GP regression (GPR) models. It is closely related to semi-supervised learning based on support vector regression (SVR) and maximum margin clustering. The proposed algorithm is simple and easy to implement. It gives a sparse solution directly unlike the SVR based algorithm. Also, the hyperparameters are estimated easily without resorting to expensive cross-validation technique. Use of sparse GPR model helps in making the proposed algorithm scalable. Preliminary results on synthetic and real-world data sets demonstrate the efficacy of the new algorithm.

A Shapley Value-Based Approach to Discover Influential Nodes in Social Networks

Our study concerns an important current problem, that of diffusion of information in social networks. This problem has received significant attention from the Internet research community in the recent times, driven by many potential applications such as viral marketing and sales promotions. In this paper, we focus on the target set selection problem, which involves discovering a small subset of influential players in a given social network, to perform a certain task of information diffusion. The target set selection problem manifests in two forms: 1) top-k nodes problem and 2) lambda-coverage problem. In the top-k nodes problem, we are required to find a set of k key nodes that would maximize the number of nodes being influenced in the network. The lambda-coverage problem is concerned with finding a set of k key nodes having minimal size that can influence a given percentage lambda of the nodes in the entire network. We propose a new way of solving these problems using the concept of Shapley value which is a well known solution concept in cooperative game theory. Our approach leads to algorithms which we call the ShaPley value-based Influential Nodes (SPINs) algorithms for solving the top-k nodes problem and the lambda-coverage problem. We compare the performance of the proposed SPIN algorithms with well known algorithms in the literature. Through extensive experimentation on four synthetically generated random graphs and six real-world data sets (Celegans, Jazz, NIPS coauthorship data set, Netscience data set, High-Energy Physics data set, and Political Books data set), we show that the proposed SPIN approach is more powerful and computationally efficient. Note to Practitioners-In recent times, social networks have received a high level of attention due to their proven ability in improving the performance of web search, recommendations in collaborative filtering systems, spreading a technology in the market using viral marketing techniques, etc. It is well known that the interpersonal relationships (or ties or links) between individuals cause change or improvement in the social system because the decisions made by individuals are influenced heavily by the behavior of their neighbors. An interesting and key problem in social networks is to discover the most influential nodes in the social network which can influence other nodes in the social network in a strong and deep way. This problem is called the target set selection problem and has two variants: 1) the top-k nodes problem, where we are required to identify a set of k influential nodes that maximize the number of nodes being influenced in the network and 2) the lambda-coverage problem which involves finding a set of influential nodes having minimum size that can influence a given percentage lambda of the nodes in the entire network. There are many existing algorithms in the literature for solving these problems. In this paper, we propose a new algorithm which is based on a novel interpretation of information diffusion in a social network as a cooperative game. Using this analogy, we develop an algorithm based on the Shapley value of the underlying cooperative game. The proposed algorithm outperforms the existing algorithms in terms of generality or computational complexity or both. Our results are validated through extensive experimentation on both synthetically generated and real-world data sets.

Chance constrained uncertain classification via robust optimization

This paper studies the problem of constructing robust classifiers when the training is plagued with uncertainty. The problem is posed as a Chance-Constrained Program (CCP) which ensures that the uncertain data points are classified correctly with high probability. Unfortunately such a CCP turns out to be intractable. The key novelty is in employing Bernstein bounding schemes to relax the CCP as a convex second order cone program whose solution is guaranteed to satisfy the probabilistic constraint. Prior to this work, only the Chebyshev based relaxations were exploited in learning algorithms. Bernstein bounds employ richer partial information and hence can be far less conservative than Chebyshev bounds. Due to this efficient modeling of uncertainty, the resulting classifiers achieve higher classification margins and hence better generalization. Methodologies for classifying uncertain test data points and error measures for evaluating classifiers robust to uncertain data are discussed. Experimental results on synthetic and real-world datasets show that the proposed classifiers are better equipped to handle data uncertainty and outperform state-of-the-art in many cases.

Robust Formulations for Handling Uncertainty in Kernel Matrices

We study the problem of uncertainty in the entries of the Kernel matrix, arising in SVM formulation. Using Chance Constraint Programming and a novel large deviation inequality we derive a formulation which is robust to such noise. The resulting formulation applies when the noise is Gaussian, or has finite support. The formulation in general is non-convex, but in several cases of interest it reduces to a convex program. The problem of uncertainty in kernel matrix is motivated from the real world problem of classifying proteins when the structures are provided with some uncertainty. The formulation derived here naturally incorporates such uncertainty in a principled manner leading to significant improvements over the state of the art. 1.

Efficient algorithms for learning kernels from multiple similarity matrices with general convex loss functions

In this paper we consider the problem of learning an n × n kernel matrix from m(1) similarity matrices under general convex loss. Past research have extensively studied the m = 1 case and have derived several algorithms which require sophisticated techniques like ACCP, SOCP, etc. The existing algorithms do not apply if one uses arbitrary losses and often can not handle m > 1 case. We present several provably convergent iterative algorithms, where each iteration requires either an SVM or a Multiple Kernel Learning (MKL) solver for m > 1 case. One of the major contributions of the paper is to extend the well knownMirror Descent(MD) framework to handle Cartesian product of psd matrices. This novel extension leads to an algorithm, called EMKL, which solves the problem in O(m2 log n 2) iterations; in each iteration one solves an MKL involving m kernels and m eigen-decomposition of n × n matrices. By suitably defining a restriction on the objective function, a faster version of EMKL is proposed, called REKL,which avoids the eigen-decomposition. An alternative to both EMKL and REKL is also suggested which requires only an SVMsolver. Experimental results on real world protein data set involving several similarity matrices illustrate the efficacy of the proposed algorithms.

Believe it or Not! Multicore CPUs can Match GPUs for FLOP-intensive Applications

In this work, we evaluate performance of a real-world image processing application that uses a cross-correlation algorithm to compare a given image with a reference one. The algorithm processes individual images represented as 2-dimensional matrices of single-precision floating-point values using O(n4) operations involving dot-products and additions. We implement this algorithm on a nVidia GTX 285 GPU using CUDA, and also parallelize it for the Intel Xeon (Nehalem) and IBM Power7 processors, using both manual and automatic techniques. Pthreads and OpenMP with SSE and VSX vector intrinsics are used for the manually parallelized version, while a state-of-the-art optimization framework based on the polyhedral model is used for automatic compiler parallelization and optimization. The performance of this algorithm on the nVidia GPU suffers from: (1) a smaller shared memory, (2) unaligned device memory access patterns, (3) expensive atomic operations, and (4) weaker single-thread performance. On commodity multi-core processors, the application dataset is small enough to fit in caches, and when parallelized using a combination of task and short-vector data parallelism (via SSE/VSX) or through fully automatic optimization from the compiler, the application matches or beats the performance of the GPU version. The primary reasons for better multi-core performance include larger and faster caches, higher clock frequency, higher on-chip memory bandwidth, and better compiler optimization and support for parallelization. The best performing versions on the Power7, Nehalem, and GTX 285 run in 1.02s, 1.82s, and 1.75s, respectively. These results conclusively demonstrate that, under certain conditions, it is possible for a FLOP-intensive structured application running on a multi-core processor to match or even beat the performance of an equivalent GPU version.

Environment Education for Ecosystem Conservation

Conservation of natural resources through sustainable ecosystem management and development is the key to our secured future. The management of ecosystem involves inventorying and monitoring, and applying integrated technologies, methodologies and interdisciplinary approaches for its conservation. Hence, now it is even more critical than ever before for the humans to be environmentally literate. To realise this vision, both ecological and environmental education must become a fundamental part of the education system at all levels of education. Currently, it is even more critical than ever before for the humankind as a whole to have a clear understanding of environmental concerns and to follow sustainable development practices. The degradation of our environment is linked to continuing problems of pollution, loss of forest, solid waste disposal, and issues related to economic productivity and national as well as ecological security. Environmental management has gained momentum in the recent years with the initiatives focussing on managing environmental hazards and preventing possible disasters. Environmental issues make better sense, when one can understand them in the context of one’s own cognitive sphere. Environmental education focusing on real-world contexts and issues often begins close to home, encouraging learners to understand and forge connections with their immediate surroundings. The awareness, knowledge, and skills needed for these local connections and understandings provide a base for moving out into larger systems, broader issues, and a more sophisticated comprehension of causes, connections, and consequences. Environmental Education Programme at CES in collaboration with Karnataka Environment Research Foundation (KERF) referred as ‘Know your Ecosystem’ focuses on the importance of investigating the ecosystems within the context of human influences, incorporating an examination of ecology, economics, culture, political structure, and social equity as well as natural processes and systems. The ultimate goal of environment education is to develop an environmentally literate public. It needs to address the connection between our conception and practice of education and our relationship as human cultures to life-sustaining ecological systems. For each environmental issue there are many perspectives and much uncertainty. Environmental education cultivates the ability to recognise uncertainty, envision alternative scenarios, and adapt to changing conditions and information. These knowledge, skills, and mindset translate into a citizenry who is better equipped to address its common problems and take advantage of opportunities, whether environmental concerns are involved or not.

Issues in Achievement of Haptic Realism

This paper deals with haptic realism related to Kinematic capabilities of the devices used in manipulation of virtual objects in virtual assembly environments and its effect on achieving haptic realism. Haptic realism implies realistic touch sensation. In virtual world all the operations are to be performed in the same way and with same level of accuracy as in the real world .In order to achieve realism there should be a complete mapping of real and virtual world dimensions. Experiments are conducted to know the kinematic capabilities of the device by comparing the dimensions of the object in the real and virtual world. Registered dimensions in the virtual world are found to be approximately 1.5 times that of the real world. Dimensional variations observed were discrepancy due to exoskeleton and discrepancy due to real and virtual hands. Experiments are conducted to know the discrepancy due to exoskeleton and this discrepancy can be taken care of by either at the hardware or software level. A Mathematical model is proposed to know the discrepancy between real and virtual hands. This could not give a fixed value and can not be taken care of by calibration. Experiments are conducted to figure out how much compensation can be given to achieve haptic realism.

Environment Education for Ecosystem Conservation

Conservation of natural resources through sustainable ecosystem management and development is the key to our secured future. The management of ecosystem involves inventorying and monitoring, and applying integrated technologies, methodologies and interdisciplinary approaches for its conservation. Hence, now it is even more critical than ever before for the humans to be environmentally literate. To realise this vision, both ecological and environmental education must become a fundamental part of the education system at all levels of education. Currently, it is even more critical than ever before for the humankind as a whole to have a clear understanding of environmental concerns and to follow sustainable development practices. The degradation of our environment is linked to continuing problems of pollution, loss of forest, solid waste disposal, and issues related to economic productivity and national as well as ecological security. Environmental management has gained momentum in the recent years with the initiatives focussing on managing environmental hazards and preventing possible disasters. Environmental issues make better sense, when one can understand them in the context of one’s own cognitive sphere. Environmental education focusing on real-world contexts and issues often begins close to home, encouraging learners to understand and forge connections with their immediate surroundings. The awareness, knowledge, and skills needed for these local connections and understandings provide a base for moving out into larger systems, broader issues, and a more sophisticated comprehension of causes, connections, and consequences. Environmental Education Programme at CES in collaboration with Karnataka Environment Research Foundation (KERF) referred as ‘Know your Ecosystem’ focuses on the importance of investigating the ecosystems within the context of human influences, incorporating an examination of ecology, economics, culture, political structure, and social equity as well as natural processes and systems. The ultimate goal of environment education is to develop an environmentally literate public. It needs to address the connection between our conception and practice of education and our relationship as human cultures to life-sustaining ecological systems. For each environmental issue there are many perspectives and much uncertainty. Environmental education cultivates the ability to recognise uncertainty, envision alternative scenarios, and adapt to changing conditions and information. These knowledge, skills, and mindset translate into a citizenry who is better equipped to address its common problems and take advantage of opportunities, whether environmental concerns are involved or not.

Multiclass Core Vector Machine

Even though several techniques have been proposed in the literature for achieving multiclass classification using Support Vector Machine(SVM), the scalability aspect of these approaches to handle large data sets still needs much of exploration. Core Vector Machine(CVM) is a technique for scaling up a two class SVM to handle large data sets. In this paper we propose a Multiclass Core Vector Machine(MCVM). Here we formulate the multiclass SVM problem as a Quadratic Programming(QP) problem defining an SVM with vector valued output. This QP problem is then solved using the CVM technique to achieve scalability to handle large data sets. Experiments done with several large synthetic and real world data sets show that the proposed MCVM technique gives good generalization performance as that of SVM at a much lesser computational expense. Further, it is observed that MCVM scales well with the size of the data set.

Rough Core Vector Clustering

Support Vector Clustering has gained reasonable attention from the researchers in exploratory data analysis due to firm theoretical foundation in statistical learning theory. Hard Partitioning of the data set achieved by support vector clustering may not be acceptable in real world scenarios. Rough Support Vector Clustering is an extension of Support Vector Clustering to attain a soft partitioning of the data set. But the Quadratic Programming Problem involved in Rough Support Vector Clustering makes it computationally expensive to handle large datasets. In this paper, we propose Rough Core Vector Clustering algorithm which is a computationally efficient realization of Rough Support Vector Clustering. Here Rough Support Vector Clustering problem is formulated using an approximate Minimum Enclosing Ball problem and is solved using an approximate Minimum Enclosing Ball finding algorithm. Experiments done with several Large Multi class datasets such as Forest cover type, and other Multi class datasets taken from LIBSVM page shows that the proposed strategy is efficient, finds meaningful soft cluster abstractions which provide a superior generalization performance than the SVM classifier.

Environment Education for Ecosystem Conservation

Conservation of natural resources through sustainable ecosystem management and development is the key to our secured future. The management of ecosystem involves inventorying and monitoring, and applying integrated technologies, methodologies and interdisciplinary approaches for its conservation. Hence, now it is even more critical than ever before for the humans to be environmentally literate. To realise this vision, both ecological and environmental education must become a fundamental part of the education system at all levels of education. Currently, it is even more critical than ever before for the humankind as a whole to have a clear understanding of environmental concerns and to follow sustainable development practices. The degradation of our environment is linked to continuing problems of pollution, loss of forest, solid waste disposal, and issues related to economic productivity and national as well as ecological security. Environmental management has gained momentum in the recent years with the initiatives focussing on managing environmental hazards and preventing possible disasters. Environmental issues make better sense, when one can understand them in the context of one’s own cognitive sphere. Environmental education focusing on real-world contexts and issues often begins close to home, encouraging learners to understand and forge connections with their immediate surroundings. The awareness, knowledge, and skills needed for these local connections and understandings provide a base for moving out into larger systems, broader issues, and a more sophisticated comprehension of causes, connections, and consequences. Environmental Education Programme at CES in collaboration with Karnataka Environment Research Foundation (KERF) referred as ‘Know your Ecosystem’ focuses on the importance of investigating the ecosystems within the context of human influences, incorporating an examination of ecology, economics, culture, political structure, and social equity as well as natural processes and systems. The ultimate goal of environment education is to develop an environmentally literate public. It needs to address the connection between our conception and practice of education and our relationship as human cultures to life-sustaining ecological systems. For each environmental issue there are many perspectives and much uncertainty. Environmental education cultivates the ability to recognise uncertainty, envision alternative scenarios, and adapt to changing conditions and information. These knowledge, skills, and mindset translate into a citizenry who is better equipped to address its common problems and take advantage of opportunities, whether environmental concerns are involved or not.