A regularized linear classifier for effective text classification

In document community support vector machines and naïve bayes classifier are known for their simplistic yet excellent performance. Normally the feature subsets used by these two approaches complement each other, however a little has been done to combine them. The essence of this paper is a linear classifier, very similar to these two. We propose a novel way of combining these two approaches, which synthesizes best of them into a hybrid model. We evaluate the proposed approach using 20ng dataset, and compare it with its counterparts. The efficacy of our results strongly corroborate the effectiveness of our approach.

Discriminative feature analysis and selection for document classification

Classification of a large document collection involves dealing with a huge feature space where each distinct word is a feature. In such an environment, classification is a costly task both in terms of running time and computing resources. Further it will not guarantee optimal results because it is likely to overfit by considering every feature for classification. In such a context, feature selection is inevitable. This work analyses the feature selection methods, explores the relations among them and attempts to find a minimal subset of features which are discriminative for document classification.

Feature selection for unsupervised learning

In this paper, we present a methodology for identifying best features from a large feature space. In high dimensional feature space nearest neighbor search is meaningless. In this feature space we see quality and performance issue with nearest neighbor search. Many data mining algorithms use nearest neighbor search. So instead of doing nearest neighbor search using all the features we need to select relevant features. We propose feature selection using Non-negative Matrix Factorization(NMF) and its application to nearest neighbor search. Recent clustering algorithm based on Locally Consistent Concept Factorization(LCCF) shows better quality of document clustering by using local geometrical and discriminating structure of the data. By using our feature selection method we have shown further improvement of performance in the clustering.

Hybrid online non-negative matrix factorization for clustering of documents

When document corpus is very large, we often need to reduce the number of features. But it is not possible to apply conventional Non-negative Matrix Factorization(NMF) on billion by million matrix as the matrix may not fit in memory. Here we present novel Online NMF algorithm. Using Online NMF, we reduced original high-dimensional space to low-dimensional space. Then we cluster all the documents in reduced dimension using k-means algorithm. We experimentally show that by processing small subsets of documents we will be able to achieve good performance. The method proposed outperforms existing algorithms.

Projecting low and extensive dimensional chaos from spatio-temporal dynamics

We review the spatio-temporal dynamical features of the Ananthakrishna model for the Portevin-Le Chatelier effect, a kind of plastic instability observed under constant strain rate deformation conditions. We then establish a qualitative correspondence between the spatio-temporal structures that evolve continuously in the instability domain and the nature of the irregularity of the scalar stress signal. Rest of the study is on quantifying the dynamical information contained in the stress signals about the spatio-temporal dynamics of the model. We show that at low applied strain rates, there is a one-to-one correspondence with the randomly nucleated isolated bursts of mobile dislocation density and the stress drops. We then show that the model equations are spatio-temporally chaotic by demonstrating the number of positive Lyapunov exponents and Lyapunov dimension scale with the system size at low and high strain rates. Using a modified algorithm for calculating correlation dimension density, we show that the stress-strain signals at low applied strain rates corresponding to spatially uncorrelated dislocation bands exhibit features of low dimensional chaos. This is made quantitative by demonstrating that the model equations can be approximately reduced to space independent model equations for the average dislocation densities, which is known to be low-dimensionally chaotic. However, the scaling regime for the correlation dimension shrinks with increasing applied strain rate due to increasing propensity for propagation of the dislocation bands. The stress signals in the partially propagating to fully propagating bands turn to have features of extensive chaos.

Data assimilation using ensemble transform Kalman filter (ETKF) in ROMS model for Indian Ocean

Study of Oceans dynamics and forecast is crucial as it influences the regional climate and other marine activities. Forecasting oceanographic states like sea surface currents, Sea surface temperature (SST) and mixed layer depth at different time scales is extremely important for these activities. These forecasts are generated by various ocean general circulation models (OGCM). One such model is the Regional Ocean Modelling System (ROMS). Though ROMS can simulate several features of ocean, it cannot reproduce the thermocline of the ocean properly. Solution to this problem is to incorporates data assimilation (DA) in the model. DA system using Ensemble Transform Kalman Filter (ETKF) has been developed for ROMS model to improve the accuracy of the model forecast. To assimilate data temperature and salinity from ARGO data has been used as observation. Assimilated temperature and salinity without localization shows oscillations compared to the model run without assimilation for India Ocean. Same was also found for u and v-velocity fields. With localization we found that the state variables are diverging within the localization scale.

Role of silica nanoparticles in conductivity enhancement of nanocomposite solid polymer electrolytes: (PEG(x) NaBr): ySiO(2)

Nanocomposite solid polymer electrolytes (NCSPEs) with conducting species other than Li ions are being investigated for solid-state battery applications. Pristine solid polymer electrolytes (SPEs) do not show ionic conductivity suitable for batteries. Addition of inert fillers to SPEs is known to enhance the ionic conductivity. In this paper, we present the role of silica nanoparticles in enhancing the ionic conductivity in NCSPEs with sodium as conducting species. Sodium bromide is complexed with the host polyethylene glycol polymer by solution cast method and silica nanoparticles (SiO2, average particle size 7 nm) are incorporated into the complex in small amounts. The composites are characterized by powder XRD and IR spectroscopy. Conductivity measurements are undertaken as a function of concentration of salt and also as a function of temperature using impedance spectroscopy. Addition of silica nanoparticles shows an enhancement in conductivity by 1-2 orders of magnitude. The results are discussed in terms of interaction of nanoparticles with the nonconducting anions.

Entropy of quantum states: Ambiguities

The von Neumann entropy of a generic quantum state is not unique unless the state can be uniquely decomposed as a sum of extremal or pure states. As pointed out to us by Sorkin, this happens if the GNS representation (of the algebra of observables in some quantum state) is reducible, and some representations in the decomposition occur with non-trivial degeneracy. This non-unique entropy can occur at zero temperature. We will argue elsewhere in detail that the degeneracies in the GNS representation can be interpreted as an emergent broken gauge symmetry, and play an important role in the analysis of emergent entropy due to non-Abelian anomalies. Finally, we establish the analogue of an H-theorem for this entropy by showing that its evolution is Markovian, determined by a stochastic matrix.

Rainbow colouring of split and threshold Graphs

A rainbow colouring of a connected graph is a colouring of the edges of the graph, such that every pair of vertices is connected by at least one path in which no two edges are coloured the same. Such a colouring using minimum possible number of colours is called an optimal rainbow colouring, and the minimum number of colours required is called the rainbow connection number of the graph. A Chordal Graph is a graph in which every cycle of length more than 3 has a chord. A Split Graph is a chordal graph whose vertices can be partitioned into a clique and an independent set. A threshold graph is a split graph in which the neighbourhoods of the independent set vertices form a linear order under set inclusion. In this article, we show the following: 1. The problem of deciding whether a graph can be rainbow coloured using 3 colours remains NP-complete even when restricted to the class of split graphs. However, any split graph can be rainbow coloured in linear time using at most one more colour than the optimum. 2. For every integer k ≥ 3, the problem of deciding whether a graph can be rainbow coloured using k colours remains NP-complete even when restricted to the class of chordal graphs. 3. For every positive integer k, threshold graphs with rainbow connection number k can be characterised based on their degree sequence alone. Further, we can optimally rainbow colour a threshold graph in linear time.

Polynomial time and parameterized approximation algorithms for boxicity

The boxicity (cubicity) of a graph G, denoted by box(G) (respectively cub(G)), is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes (cubes) in ℝ k . The problem of computing boxicity (cubicity) is known to be inapproximable in polynomial time even for graph classes like bipartite, co-bipartite and split graphs, within an O(n 0.5 − ε ) factor for any ε > 0, unless NP = ZPP. We prove that if a graph G on n vertices has a clique on n − k vertices, then box(G) can be computed in time n22O(k2logk) . Using this fact, various FPT approximation algorithms for boxicity are derived. The parameter used is the vertex (or edge) edit distance of the input graph from certain graph families of bounded boxicity - like interval graphs and planar graphs. Using the same fact, we also derive an O(nloglogn√logn√) factor approximation algorithm for computing boxicity, which, to our knowledge, is the first o(n) factor approximation algorithm for the problem. We also present an FPT approximation algorithm for computing the cubicity of graphs, with vertex cover number as the parameter.

Compositional hierarchical monitoring automaton construction for LTL

In this paper we give a compositional (or inductive) construction of monitoring automata for LTL formulas. Our construction is similar in spirit to the compositional construction of Kesten and Pnueli [5]. We introduce the notion of hierarchical Büchi automata and phrase our constructions in the framework of these automata. We give detailed constructions for all the principal LTL operators including past operators, along with proofs of correctness of the constructions.

Model-checking bisimulation-based information flow properties for infinite state sstems

Bisimulation-based information flow properties were introduced by Focardi and Gorrieri [1] as a way of specifying security properties for transition system models. These properties were shown to be decidable for finite-state systems. In this paper, we study the problem of verifying these properties for some well-known classes of infinite state systems. We show that all the properties are undecidable for each of these classes of systems.

Scalable flow-sensitive pointer analysis for fava with strong updates

The ability to perform strong updates is the main contributor to the precision of flow-sensitive pointer analysis algorithms. Traditional flow-sensitive pointer analyses cannot strongly update pointers residing in the heap. This is a severe restriction for Java programs. In this paper, we propose a new flow-sensitive pointer analysis algorithm for Java that can perform strong updates on heap-based pointers effectively. Instead of points-to graphs, we represent our points-to information as maps from access paths to sets of abstract objects. We have implemented our analysis and run it on several large Java benchmarks. The results show considerable improvement in precision over the points-to graph based flow-insensitive and flow-sensitive analyses, with reasonable running time.

Mechanism design for time critical and cost critical task execution via crowdsourcing

An exciting application of crowdsourcing is to use social networks in complex task execution. In this paper, we address the problem of a planner who needs to incentivize agents within a network in order to seek their help in executing an atomic task as well as in recruiting other agents to execute the task. We study this mechanism design problem under two natural resource optimization settings: (1) cost critical tasks, where the planner's goal is to minimize the total cost, and (2) time critical tasks, where the goal is to minimize the total time elapsed before the task is executed. We identify a set of desirable properties that should ideally be satisfied by a crowdsourcing mechanism. In particular, sybil-proofness and collapse-proofness are two complementary properties in our desiderata. We prove that no mechanism can satisfy all the desirable properties simultaneously. This leads us naturally to explore approximate versions of the critical properties. We focus our attention on approximate sybil-proofness and our exploration leads to a parametrized family of payment mechanisms which satisfy collapse-proofness. We characterize the approximate versions of the desirable properties in cost critical and time critical domain.

Sufficient conditions for formation of a network topology by self-interested agents

Networks such as organizational network of a global company play an important role in a variety of knowledge management and information diffusion tasks. The nodes in these networks correspond to individuals who are self-interested. The topology of these networks often plays a crucial role in deciding the ease and speed with which certain tasks can be accomplished using these networks. Consequently, growing a stable network having a certain topology is of interest. Motivated by this, we study the following important problem: given a certain desired network topology, under what conditions would best response (link addition/deletion) strategies played by self-interested agents lead to formation of a pairwise stable network with only that topology. We study this interesting reverse engineering problem by proposing a natural model of recursive network formation. In this model, nodes enter the network sequentially and the utility of a node captures principal determinants of network formation, namely (1) benefits from immediate neighbors, (2) costs of maintaining links with immediate neighbors, (3) benefits from indirect neighbors, (4) bridging benefits, and (5) network entry fee. Based on this model, we analyze relevant network topologies such as star graph, complete graph, bipartite Turan graph, and multiple stars with interconnected centers, and derive a set of sufficient conditions under which these topologies emerge as pairwise stable networks. We also study the social welfare properties of the above topologies.