OpenRaiser/Intern-Atlas huggingface dataset:
Inverse Covariance Estimation for High-Dimensional Data in Linear Time and Space: Spectral Methods for Riccati and Sparse Models
Venue: arXiv cs.LG 2013
Year: 2013

We propose maximum likelihood estimation for learning Gaussian graphical models with a Gaussian (ell_2^2) prior on the parameters. This is in contrast to the commonly used Laplace (ell_1) prior for encouraging sparseness. We show that our optimization problem leads to a Riccati matrix equation, which has a closed form solution. We propose an efficient algorithm that performs a singular value decomposition of the training data. Our algorithm is O(NT^2)-time and O(NT)-space for N variables and T samples. Our method is tailored to high-dimensional problems (N gg T), in which sparseness promoting methods become intractable. Furthermore, instead of obtaining a single solution for a specific regularization parameter, our algorithm finds the whole solution path. We show that the method has logarithmic sample complexity under the spiked covariance model. We also propose sparsification of the dense solution with provable performance guarantees. We provide techniques for using our learnt models, such as removing unimportant variables, computing likelihoods and conditional distributions. Finally, we show promising results in several gene expressions datasets.
Evaluating Anytime Algorithms for Learning Optimal Bayesian Networks
Venue: arXiv cs.AI 2013
Year: 2013

Exact algorithms for learning Bayesian networks guarantee to find provably optimal networks. However, they may fail in difficult learning tasks due to limited time or memory. In this research we adapt several anytime heuristic search-based algorithms to learn Bayesian networks. These algorithms find high-quality solutions quickly, and continually improve the incumbent solution or prove its optimality before resources are exhausted. Empirical results show that the anytime window A* algorithm usually finds higher-quality, often optimal, networks more quickly than other approaches. The results also show that, surprisingly, while generating networks with few parents per variable are structurally simpler, they are harder to learn than complex generating networks with more parents per variable.
Stochastic Rank Aggregation
Venue: arXiv cs.LG 2013
Year: 2013

This paper addresses the problem of rank aggregation, which aims to find a consensus ranking among multiple ranking inputs. Traditional rank aggregation methods are deterministic, and can be categorized into explicit and implicit methods depending on whether rank information is explicitly or implicitly utilized. Surprisingly, experimental results on real data sets show that explicit rank aggregation methods would not work as well as implicit methods, although rank information is critical for the task. Our analysis indicates that the major reason might be the unreliable rank information from incomplete ranking inputs. To solve this problem, we propose to incorporate uncertainty into rank aggregation and tackle the problem in both unsupervised and supervised scenario. We call this novel framework {stochastic rank aggregation} (St.Agg for short). Specifically, we introduce a prior distribution on ranks, and transform the ranking functions or objectives in traditional explicit methods to their expectations over this distribution. Our experiments on benchmark data sets show that the proposed St.Agg outperforms the baselines in both unsupervised and supervised scenarios.
Preference Elicitation For General Random Utility Models
Venue: arXiv cs.AI 2013
Year: 2013

This paper discusses {General Random Utility Models (GRUMs)}. These are a class of parametric models that generate partial ranks over alternatives given attributes of agents and alternatives. We propose two preference elicitation scheme for GRUMs developed from principles in Bayesian experimental design, one for social choice and the other for personalized choice. We couple this with a general Monte-Carlo-Expectation-Maximization (MC-EM) based algorithm for MAP inference under GRUMs. We also prove uni-modality of the likelihood functions for a class of GRUMs. We examine the performance of various criteria by experimental studies, which show that the proposed elicitation scheme increases the precision of estimation.
Modeling Documents with Deep Boltzmann Machines
Venue: arXiv cs.LG 2013
Year: 2013

We introduce a Deep Boltzmann Machine model suitable for modeling and extracting latent semantic representations from a large unstructured collection of documents. We overcome the apparent difficulty of training a DBM with judicious parameter tying. This parameter tying enables an efficient pretraining algorithm and a state initialization scheme that aids inference. The model can be trained just as efficiently as a standard Restricted Boltzmann Machine. Our experiments show that the model assigns better log probability to unseen data than the Replicated Softmax model. Features extracted from our model outperform LDA, Replicated Softmax, and DocNADE models on document retrieval and document classification tasks.
Dynamic Blocking and Collapsing for Gibbs Sampling
Venue: arXiv cs.AI 2013
Year: 2013

In this paper, we investigate combining blocking and collapsing -- two widely used strategies for improving the accuracy of Gibbs sampling -- in the context of probabilistic graphical models (PGMs). We show that combining them is not straight-forward because collapsing (or eliminating variables) introduces new dependencies in the PGM and in computation-limited settings, this may adversely affect blocking. We therefore propose a principled approach for tackling this problem. Specifically, we develop two scoring functions, one each for blocking and collapsing, and formulate the problem of partitioning the variables in the PGM into blocked and collapsed subsets as simultaneously maximizing both scoring functions (i.e., a multi-objective optimization problem). We propose a dynamic, greedy algorithm for approximately solving this intractable optimization problem. Our dynamic algorithm periodically updates the partitioning into blocked and collapsed variables by leveraging correlation statistics gathered from the generated samples and enables rapid mixing by blocking together and collapsing highly correlated variables. We demonstrate experimentally the clear benefit of our dynamic approach: as more samples are drawn, our dynamic approach significantly outperforms static graph-based approaches by an order of magnitude in terms of accuracy.
Calculation of Entailed Rank Constraints in Partially Non-Linear and Cyclic Models
Venue: arXiv cs.AI 2013
Year: 2013

The Trek Separation Theorem (Sullivant et al. 2010) states necessary and sufficient conditions for a linear directed acyclic graphical model to entail for all possible values of its linear coefficients that the rank of various sub-matrices of the covariance matrix is less than or equal to n, for any given n. In this paper, I extend the Trek Separation Theorem in two ways: I prove that the same necessary and sufficient conditions apply even when the generating model is partially non-linear and contains some cycles. This justifies application of constraint-based causal search algorithms such as the BuildPureClusters algorithm (Silva et al. 2006) for discovering the causal structure of latent variable models to data generated by a wider class of causal models that may contain non-linear and cyclic relations among the latent variables.
On the Internal Dynamics of the Shanghai Ranking
Venue: arXiv cs.DL 2013
Year: 2013

The Academic Ranking of World Universities (ARWU) published by researchers at Shanghai Jiao Tong University has become a major source of information for university administrators, country officials, students and the public at large. Recent discoveries regarding its internal dynamics allow the inversion of published ARWU indicator scores to reconstruct raw scores for five hundred world class universities. This paper explores raw scores in the ARWU and in other contests to contrast the dynamics of rank-driven and score-driven tables, and to explain why the ARWU ranking is a score-driven procedure. We show that the ARWU indicators constitute sub-scales of a single factor accounting for research performance, and provide an account of the system of gains and non-linearities used by ARWU. The paper discusses the non-linearities selected by ARWU, concluding that they are designed to represent the regressive character of indicators measuring research performance. We propose that the utility and usability of the ARWU could be greatly improved by replacing the unwanted dynamical effects of the annual re-scaling based on raw scores of the best performers.
Total Jensen divergences: Definition, Properties and k-Means++ Clustering
Venue: arXiv cs.IT 2013
Year: 2013

We present a novel class of divergences induced by a smooth convex function called total Jensen divergences. Those total Jensen divergences are invariant by construction to rotations, a feature yielding regularization of ordinary Jensen divergences by a conformal factor. We analyze the relationships between this novel class of total Jensen divergences and the recently introduced total Bregman divergences. We then proceed by defining the total Jensen centroids as average distortion minimizers, and study their robustness performance to outliers. Finally, we prove that the k-means++ initialization that bypasses explicit centroid computations is good enough in practice to guarantee probabilistically a constant approximation factor to the optimal k-means clustering.
A Low-Voltage, Low-Power 4-bit BCD Adder, designed using the Clock Gated Power Gating, and the DVT Scheme
Venue: arXiv cs.AR 2013
Year: 2013

This paper proposes a Low-Power, Energy Efficient 4-bit Binary Coded Decimal (BCD) adder design where the conventional 4-bit BCD adder has been modified with the Clock Gated Power Gating Technique. Moreover, the concept of DVT (Dual-vth) scheme has been introduced while designing the full adder blocks to reduce the Leakage Power, as well as, to maintain the overall performance of the entire circuit. The reported architecture of 4-bit BCD adder is designed using 45 nm technology and it consumes 1.384 μWatt of Average Power while operating with a frequency of 200 MHz, and a Supply Voltage (Vdd) of 1 Volt. The results obtained from different simulation runs on SPICE, indicate the superiority of the proposed design compared to the conventional 4-bit BCD adder. Considering the product of Average Power and Delay, for the operating frequency of 200 MHz, a fair 47.41 % reduction compared to the conventional design has been achieved with this proposed scheme.
An Efficient Index for Visual Search in Appearance-based SLAM
Venue: arXiv cs.CV 2013
Year: 2013

Vector-quantization can be a computationally expensive step in visual bag-of-words (BoW) search when the vocabulary is large. A BoW-based appearance SLAM needs to tackle this problem for an efficient real-time operation. We propose an effective method to speed up the vector-quantization process in BoW-based visual SLAM. We employ a graph-based nearest neighbor search (GNNS) algorithm to this aim, and experimentally show that it can outperform the state-of-the-art. The graph-based search structure used in GNNS can efficiently be integrated into the BoW model and the SLAM framework. The graph-based index, which is a k-NN graph, is built over the vocabulary words and can be extracted from the BoW's vocabulary construction procedure, by adding one iteration to the k-means clustering, which adds small extra cost. Moreover, exploiting the fact that images acquired for appearance-based SLAM are sequential, GNNS search can be initiated judiciously which helps increase the speedup of the quantization process considerably.
Adopting level set theory based algorithms to segment human ear
Venue: arXiv cs.CV 2013
Year: 2013

Human identification has always been a topic that interested researchers around the world. Biometric methods are found to be more effective and much easier for the users than the traditional identification methods like keys, smart cards and passwords. Unlike with the traditional methods, with biometric methods the data acquisition is most of the times passive, which means the users do not take active part in data acquisition. Data acquisition can be performed using cameras, scanners or sensors. Human physiological biometrics such as face, eye and ear are good candidates for uniquely identifying an individual. However, human ear scores over face and eye because of certain advantages it has over face. The most challenging phase in human identification based on ear biometric is the segmentation of the ear image from the captured image which may contain many unwanted details. In this work, PDE based image processing techniques are used to segment out the ear image. Level Set Theory based image processing is employed to obtain the contour of the ear image. A few Level set algorithms are compared for their efficiency in segmenting test ear images.
Development and Transcription of Assamese Speech Corpus
Venue: arXiv cs.CL 2013
Year: 2013

A balanced speech corpus is the basic need for any speech processing task. In this report we describe our effort on development of Assamese speech corpus. We mainly focused on some issues and challenges faced during development of the corpus. Being a less computationally aware language, this is the first effort to develop speech corpus for Assamese. As corpus development is an ongoing process, in this paper we report only the initial task.
Nonlinear Compressive Particle Filtering
Venue: arXiv cs.SY 2013
Year: 2013

Many systems for which compressive sensing is used today are dynamical. The common approach is to neglect the dynamics and see the problem as a sequence of independent problems. This approach has two disadvantages. Firstly, the temporal dependency in the state could be used to improve the accuracy of the state estimates. Secondly, having an estimate for the state and its support could be used to reduce the computational load of the subsequent step. In the linear Gaussian setting, compressive sensing was recently combined with the Kalman filter to mitigate above disadvantages. In the nonlinear dynamical case, compressive sensing can not be used and, if the state dimension is high, the particle filter would perform poorly. In this paper we combine one of the most novel developments in compressive sensing, nonlinear compressive sensing, with the particle filter. We show that the marriage of the two is essential and that neither the particle filter or nonlinear compressive sensing alone gives a satisfying solution.
Orthogonal Frequency Division Multiplexing and its Applications
Venue: arXiv cs.NI 2013
Year: 2013

Orthogonal Frequency Division Multiplexing (OFDM) is a multi-carrier modulation technique which is very much popular in new wireless networks of IEEE standard, digital television, audio broadcasting and 4G mobile communications. The main benefit of OFDM over single-carrier schemes is its ability to cope with severe channel conditions without complex equalization filters. It has improved the quality of long-distance communication by eliminating InterSymbol Interference (ISI) and improving Signal-to-Noise ratio (SNR). The main drawbacks of OFDM are its high peak to average power ratio and its sensitivity to phase noise and frequency offset. This paper gives an overview of OFDM, its applications in various systems such as IEEE 802.11a, Digital Audio Broadcasting (DAB) and Digital Broadcast Services to Handheld Devices (DVB-H) along with its advantages and disadvantages.
Early Stage Influenza Detection from Twitter
Venue: arXiv cs.SI 2013
Year: 2013

Influenza is an acute respiratory illness that occurs virtually every year and results in substantial disease, death and expense. Detection of Influenza in its earliest stage would facilitate timely action that could reduce the spread of the illness. Existing systems such as CDC and EISS which try to collect diagnosis data, are almost entirely manual, resulting in about two-week delays for clinical data acquisition. Twitter, a popular microblogging service, provides us with a perfect source for early-stage flu detection due to its real- time nature. For example, when a flu breaks out, people that get the flu may post related tweets which enables the detection of the flu breakout promptly. In this paper, we investigate the real-time flu detection problem on Twitter data by proposing Flu Markov Network (Flu-MN): a spatio-temporal unsupervised Bayesian algorithm based on a 4 phase Markov Network, trying to identify the flu breakout at the earliest stage. We test our model on real Twitter datasets from the United States along with baselines in multiple applications, such as real-time flu breakout detection, future epidemic phase prediction, or Influenza-like illness (ILI) physician visits. Experimental results show the robustness and effectiveness of our approach. We build up a real time flu reporting system based on the proposed approach, and we are hopeful that it would help government or health organizations in identifying flu outbreaks and facilitating timely actions to decrease unnecessary mortality.
OntoMaven: Maven-based Ontology Development and Management of Distributed Ontology Repositories
Venue: arXiv cs.SE 2013
Year: 2013

In collaborative agile ontology development projects support for modular reuse of ontologies from large existing remote repositories, ontology project life cycle management, and transitive dependency management are important needs. The Apache Maven approach has proven its success in distributed collaborative Software Engineering by its widespread adoption. The contribution of this paper is a new design artifact called OntoMaven. OntoMaven adopts the Maven-based development methodology and adapts its concepts to knowledge engineering for Maven-based ontology development and management of ontology artifacts in distributed ontology repositories.
HeteSim: A General Framework for Relevance Measure in Heterogeneous Networks
Venue: arXiv cs.IR 2013
Year: 2013

Similarity search is an important function in many applications, which usually focuses on measuring the similarity between objects with the same type. However, in many scenarios, we need to measure the relatedness between objects with different types. With the surge of study on heterogeneous networks, the relevance measure on objects with different types becomes increasingly important. In this paper, we study the relevance search problem in heterogeneous networks, where the task is to measure the relatedness of heterogeneous objects (including objects with the same type or different types). A novel measure HeteSim is proposed, which has the following attributes: (1) a uniform measure: it can measure the relatedness of objects with the same or different types in a uniform framework; (2) a path-constrained measure: the relatedness of object pairs are defined based on the search path that connect two objects through following a sequence of node types; (3) a semi-metric measure: HeteSim has some good properties (e.g., self-maximum and symmetric), that are crucial to many data mining tasks. Moreover, we analyze the computation characteristics of HeteSim and propose the corresponding quick computation strategies. Empirical studies show that HeteSim can effectively and efficiently evaluate the relatedness of heterogeneous objects.
The achievable performance of convex demixing
Venue: arXiv cs.IT 2013
Year: 2013

Demixing is the problem of identifying multiple structured signals from a superimposed, undersampled, and noisy observation. This work analyzes a general framework, based on convex optimization, for solving demixing problems. When the constituent signals follow a generic incoherence model, this analysis leads to precise recovery guarantees. These results admit an attractive interpretation: each signal possesses an intrinsic degrees-of-freedom parameter, and demixing can succeed if and only if the dimension of the observation exceeds the total degrees of freedom present in the observation.
Improved bounds for the randomized decision tree complexity of recursive majority
Venue: arXiv cs.DS 2013
Year: 2013

We consider the randomized decision tree complexity of the recursive 3-majority function. We prove a lower bound of $(1/2-δ) \cdot 2.57143^h$ for the two-sided-error randomized decision tree complexity of evaluating height $h$ formulae with error $δ\in [0,1/2)$. This improves the lower bound of $(1-2δ)(7/3)^h$ given by Jayram, Kumar, and Sivakumar (STOC'03), and the one of $(1-2δ) \cdot 2.55^h$ given by Leonardos (ICALP'13). Second, we improve the upper bound by giving a new zero-error randomized decision tree algorithm that has complexity at most $(1.007) \cdot 2.64944^h$. The previous best known algorithm achieved complexity $(1.004) \cdot 2.65622^h$. The new lower bound follows from a better analysis of the base case of the recursion of Jayram et al. The new algorithm uses a novel "interleaving" of two recursive algorithms.
An upper bound on prototype set size for condensed nearest neighbor
Venue: arXiv cs.LG 2013
Year: 2013

The condensed nearest neighbor (CNN) algorithm is a heuristic for reducing the number of prototypical points stored by a nearest neighbor classifier, while keeping the classification rule given by the reduced prototypical set consistent with the full set. I present an upper bound on the number of prototypical points accumulated by CNN. The bound originates in a bound on the number of times the decision rule is updated during training in the multiclass perceptron algorithm, and thus is independent of training set size.
GPU-powered Simulation Methodologies for Biological Systems
Venue: arXiv cs.CE 2013
Year: 2013

The study of biological systems witnessed a pervasive cross-fertilization between experimental investigation and computational methods. This gave rise to the development of new methodologies, able to tackle the complexity of biological systems in a quantitative manner. Computer algorithms allow to faithfully reproduce the dynamics of the corresponding biological system, and, at the price of a large number of simulations, it is possible to extensively investigate the system functioning across a wide spectrum of natural conditions. To enable multiple analysis in parallel, using cheap, diffused and highly efficient multi-core devices we developed GPU-powered simulation algorithms for stochastic, deterministic and hybrid modeling approaches, so that also users with no knowledge of GPUs hardware and programming can easily access the computing power of graphics engines.
The Dynamic Longest Increasing Subsequence Problem
Venue: arXiv cs.DS 2013
Year: 2013

In this paper, we construct a data structure to efficiently compute the longest increasing subsequence of a sequence subject to dynamic updates. Our data structure supports a query for the longest increasing subsequence in $O(r+\log n)$ worst-case time and supports inserts anywhere in the sequence in $O \left(r\log{n/r}\right)$ worst-case time (where $r$ is the length of the longest increasing subsequence). The same data structure with a minor modification supports $O(\log n)$ worst-case time insertions if the insertions are performed at the end of the sequence. The data structure presented can also be augmented to support delete operations in the same worst-case time as insertions.