OpenRaiser/Intern-Atlas huggingface dataset:
A Successive Resultant Projection for Cylindrical Algebraic Decomposition
Venue: arXiv cs.SC 2014
Year: 2014

This note shows the equivalence of two projection operators which both can be used in cylindrical algebraic decomposition (CAD) . One is known as Brown's Projection (C. W. Brown (2001)); the other was proposed by Lu Yang in his earlier work (L.Yang and S.~H. Xia (2000)) that is sketched as follows: given a polynomial $f$ in $x_1,\,x_2,\,\cdots$, by $f_1$ denote the resultant of $f$ and its partial derivative with respect to $x_1$ (removing the multiple factors), by $f_2$ denote the resultant of $f_1$ and its partial derivative with respect to $x_2$, (removing the multiple factors), $\cdots$, repeat this procedure successively until the last resultant becomes a univariate polynomial. Making use of an identity, the equivalence of these two projection operators is evident.
Robust Inference for Visual-Inertial Sensor Fusion
Venue: arXiv cs.RO 2014
Year: 2014

Inference of three-dimensional motion from the fusion of inertial and visual sensory data has to contend with the preponderance of outliers in the latter. Robust filtering deals with the joint inference and classification task of selecting which data fits the model, and estimating its state. We derive the optimal discriminant and propose several approximations, some used in the literature, others new. We compare them analytically, by pointing to the assumptions underlying their approximations, and empirically. We show that the best performing method improves the performance of state-of-the-art visual-inertial sensor fusion systems, while retaining the same computational complexity.
Evaluating Haskell expressions in a tutoring environment
Venue: arXiv cs.CY 2014
Year: 2014

A number of introductory textbooks for Haskell use calculations right from the start to give the reader insight into the evaluation of expressions and the behavior of functional programs. Many programming concepts that are important in the functional programming paradigm, such as recursion, higher-order functions, pattern-matching, and lazy evaluation, can be partially explained by showing a stepwise computation. A student gets a better understanding of these concepts if she performs these evaluation steps herself. Tool support for experimenting with the evaluation of Haskell expressions is currently lacking. In this paper we present a prototype implementation of a stepwise evaluator for Haskell expressions that supports multiple evaluation strategies, specifically targeted at education. Besides performing evaluation steps the tool also diagnoses steps that are submitted by a student, and provides feedback. Instructors can add or change function definitions without knowledge of the tool's internal implementation. We discuss some preliminary results of a small survey about the tool.
Consensus of Multi-agent Systems Under State-dependent Information Transmission
Venue: arXiv cs.SY 2014
Year: 2014

In this paper, we study the consensus problem for continuous-time and discrete-time multi-agent systems in state-dependent switching networks. In each case, we first consider the networks with fixed connectivity, in which the communication between adjacent agents always exists but the influence could possibly become negligible if the transmission distance is long enough. It is obtained that consensus can be reached under a restriction of either the decaying rate of the transmission weight or the initial states of the agents. After then we investigate the networks with state-dependent connectivity, in which the information transmission between adjacent agents gradually vanishes if their distance exceeds a fixed range. In such networks, we prove that the realization of consensus requires the validity of some initial conditions. Finally, the conclusions are applied to models with the transmission law of C-S model, opinion dynamics and the rendezvous problem, the corresponding simulations are also presented.
Sparse, guided feature connections in an Abstract Deep Network
Venue: arXiv cs.NE 2014
Year: 2014

We present a technique for developing a network of re-used features, where the topology is formed using a coarse learning method, that allows gradient-descent fine tuning, known as an Abstract Deep Network (ADN). New features are built based on observed co-occurrences, and the network is maintained using a selection process related to evolutionary algorithms. This allows coarse ex- ploration of the problem space, effective for irregular domains, while gradient descent allows pre- cise solutions. Accuracy on standard UCI and Protein-Structure Prediction problems is comparable with benchmark SVM and optimized GBML approaches, and shows scalability for addressing large problems. The discrete implementation is symbolic, allowing interpretability, while the continuous method using fine-tuning shows improved accuracy. The binary multiplexer problem is explored, as an irregular domain that does not support gradient descent learning, showing solution to the bench- mark 135-bit problem. A convolutional implementation is demonstrated on image classification, showing an error-rate of 0.79% on the MNIST problem, without a pre-defined topology. The ADN system provides a method for developing a very sparse, deep feature topology, based on observed relationships between features, that is able to find solutions in irregular domains, and initialize a network prior to gradient descent learning.
Graph Analytics using the Vertica Relational Database
Venue: arXiv cs.DB 2014
Year: 2014

Graph analytics is becoming increasingly popular, with a deluge of new systems for graph analytics having been proposed in the past few years. These systems often start from the assumption that a new storage or query processing system is needed, in spite of graph data being often collected and stored in a relational database in the first place. In this paper, we study Vertica relational database as a platform for graph analytics. We show that vertex-centric graph analysis can be translated to SQL queries, typically involving table scans and joins, and that modern column-oriented databases are very well suited to running such queries. Specifically, we present an experimental evaluation of the Vertica relational database system on a variety of graph analytics, including iterative analysis, a combination of graph and relational analyses, and more complex 1- hop neighborhood graph analytics, showing that it is competitive to two popular vertex-centric graph analytics systems, namely Giraph and GraphLab.
Privacy Policy Negotiation in Social Media
Venue: arXiv cs.SI 2014
Year: 2014

Social Media involve many shared items, such as photos, which may concern more than one user. The first challenge we address in this paper is to develop a way for users of such items to take a decision on to whom to share these items. This is not an easy problem, as users' privacy preferences for the same item may conflict, so an approach that just merges in some way the users' privacy preferences may provide unsatisfactory results. We propose a negotiation mechanism for users to agree on a compromise for the conflicts found. The second challenge we address in this paper relates to the exponential complexity of such a negotiation mechanism, which could make it too slow to be used in practice in a Social Media infrastructure. To address this, we propose heuristics that reduce the complexity of the negotiation mechanism and show how substantial benefits can be derived from the use of these heuristics through extensive experimental evaluation that compares the performance of the negotiation mechanism with and without these heuristics. Moreover, we show that one such heuristic makes the negotiation mechanism produce results fast enough to be used in actual Social Media infrastructures with near-optimal results.
Twofolds in C and C++
Venue: arXiv cs.MS 2014
Year: 2014

Here I propose C and C++ interfaces and experimental implementation for twofolds arithmetic. I introduce twofolds in my previous article entitled "Twofold fast arithmetic" for tracking floating-point inaccuracy. Testing shows, plain C enables high-performance computing with twofolds. C++ interface enables coding as easily as ordinary floating-point numbers. My goal is convincing you to try twofolds; I think assuring accuracy of math computations is worth its cost. Code and use examples available at my web site, references inside.
A Mathematical Model for Logarithmic Image Processing
Venue: arXiv cs.CV 2014
Year: 2014

In this paper, we propose a new mathematical model for image processing. It is a logarithmical one. We consider the bounded interval (-1, 1) as the set of gray levels. Firstly, we define two operations: addition <+> and real scalar multiplication <x>. With these operations, the set of gray levels becomes a real vector space. Then, defining the scalar product (.|.) and the norm || . ||, we obtain an Euclidean space of the gray levels. Secondly, we extend these operations and functions for color images. We finally show the effect of various simple operations on an image.
Energy Efficiency Evaluation of Cellular Networks Based on Spatial Distributions of Traffic Load and Power Consumption
Venue: arXiv cs.NI 2014
Year: 2014

Energy efficiency has gained its significance when service providers' operational costs burden with the rapidly growing data traffic demand in cellular networks. In this paper, we propose an energy efficiency model for Poisson-Voronoi tessellation (PVT) cellular networks considering spatial distributions of traffic load and power consumption. The spatial distributions of traffic load and power consumption are derived for a typical PVT cell, and can be directly extended to the whole PVT cellular network based on the Palm theory. Furthermore, the energy efficiency of PVT cellular networks is evaluated by taking into account traffic load characteristics, wireless channel effects and interference. Both numerical and Monte Carlo simulations are conducted to evaluate the performance of the energy efficiency model in PVT cellular networks. These simulation results demonstrate that there exist maximal limits for energy efficiency in PVT cellular networks for given wireless channel conditions and user intensity in a cell.
Capacity analysis of a multi-cell multi-antenna cooperative cellular network with co-channel interference
Venue: arXiv cs.NI 2014
Year: 2014

Characterization and modeling of co-channel interference is critical for the design and performance evaluation of realistic multi-cell cellular networks. In this paper, based on alpha stable processes, an analytical co-channel interference model is proposed for multi-cell multiple-input multi-output (MIMO) cellular networks. The impact of different channel parameters on the new interference model is analyzed numerically. Furthermore, the exact normalized downlink average capacity is derived for a multi-cell MIMO cellular network with co-channel interference. Moreover, the closed-form normalized downlink average capacity is derived for cell-edge users in the multi-cell multiple-input single-output (MISO) cooperative cellular network with co-channel interference. From the new co-channel interference model and capacity, the impact of cooperative antennas and base stations on cell-edge user performance in the multi-cell multi-antenna cellular network is investigated by numerical methods. Numerical results show that cooperative transmission can improve the capacity performance of multi-cell multi-antenna cooperative cellular networks, especially in a scenario with a high density of interfering base stations. The capacity performance gain is degraded with the increased number of cooperative antennas or base stations.
Spectrum and Energy Efficiency Evaluation of Two-Tier Femtocell networks With Partially Open Channels
Venue: arXiv cs.NI 2014
Year: 2014

Two-tier femtocell networks is an efficient communication architecture that significantly improves throughput in indoor environments with low power consumption. Traditionally, a femtocell network is usually configured to be either completely open or completely closed in that its channels are either made available to all users or used by its own users only. This may limit network flexibility and performance. It is desirable for owners of femtocell base stations if a femtocell can partially open its channels for external users access. In such scenarios, spectrum and energy efficiency becomes a critical issue in the design of femtocell network protocols and structure. In this paper, we conduct performance analysis for two-tier femtocell networks with partially open channels. In particular, we build a Markov chain to model the channel access in the femtocell network and then derive the performance metrics in terms of the blocking probabilities. Based on stationary state probabilities derived by Markov chain models, spectrum and energy efficiency are modeled and analyzed under different scenarios characterized by critical parameters, including number of femtocells in a macrocell, average number of users, and number of open channels in a femtocell. Numerical and Monte-Carlo (MC) simulation results indicate that the number of open channels in a femtocell has an adverse impact on the spectrum and energy efficiency of two-tier femtocell networks. Results in this paper provide guidelines for trading off spectrum and energy efficiency of two-tier femtocell networks by configuring different numbers of open channels in a femtocell.
Extended Recommendation Framework: Generating the Text of a User Review as a Personalized Summary
Venue: arXiv cs.IR 2014
Year: 2014

We propose to augment rating based recommender systems by providing the user with additional information which might help him in his choice or in the understanding of the recommendation. We consider here as a new task, the generation of personalized reviews associated to items. We use an extractive summary formulation for generating these reviews. We also show that the two information sources, ratings and items could be used both for estimating ratings and for generating summaries, leading to improved performance for each system compared to the use of a single source. Besides these two contributions, we show how a personalized polarity classifier can integrate the rating and textual aspects. Overall, the proposed system offers the user three personalized hints for a recommendation: rating, text and polarity. We evaluate these three components on two datasets using appropriate measures for each task.
Deep Speech: Scaling up end-to-end speech recognition
Venue: arXiv cs.CL 2014
Year: 2014

We present a state-of-the-art speech recognition system developed using end-to-end deep learning. Our architecture is significantly simpler than traditional speech systems, which rely on laboriously engineered processing pipelines; these traditional systems also tend to perform poorly when used in noisy environments. In contrast, our system does not need hand-designed components to model background noise, reverberation, or speaker variation, but instead directly learns a function that is robust to such effects. We do not need a phoneme dictionary, nor even the concept of a "phoneme." Key to our approach is a well-optimized RNN training system that uses multiple GPUs, as well as a set of novel data synthesis techniques that allow us to efficiently obtain a large amount of varied data for training. Our system, called Deep Speech, outperforms previously published results on the widely studied Switchboard Hub5'00, achieving 16.0% error on the full test set. Deep Speech also handles challenging noisy environments better than widely used, state-of-the-art commercial speech systems.
Performance Analysis of Geographic Routing Protocols in Ad Hoc Networks
Venue: arXiv cs.NI 2014
Year: 2014

Geographic routing protocols greatly reduce the requirements of topology storage and provide flexibility in the accommodation of the dynamic behavior of ad hoc networks. This paper presents performance evaluations and comparisons of two geographic routing protocols and the popular AODV protocol. The trade-offs among the average path reliabilities, average conditional delays, average conditional number of hops, and area spectral efficiencies and the effects of various parameters are illustrated for finite ad hoc networks with randomly placed mobiles. This paper uses a dual method of closed-form analysis and simple simulation that is applicable to most routing protocols and provides a much more realistic performance evaluation than has previously been possible. Some features included in the new analysis are shadowing, exclusion and guard zones, and distance-dependent fading.
Boolean function monotonicity testing requires (almost) $n^{1/2}$ non-adaptive queries
Venue: arXiv cs.CC 2014
Year: 2014

We prove a lower bound of $Ω(n^{1/2 - c})$, for all $c>0$, on the query complexity of (two-sided error) non-adaptive algorithms for testing whether an $n$-variable Boolean function is monotone versus constant-far from monotone. This improves a $\tildeΩ(n^{1/5})$ lower bound for the same problem that was recently given in [CST14] and is very close to $Ω(n^{1/2})$, which we conjecture is the optimal lower bound for this model.
Effective sampling for large-scale automated writing evaluation systems
Venue: arXiv cs.CL 2014
Year: 2014

Automated writing evaluation (AWE) has been shown to be an effective mechanism for quickly providing feedback to students. It has already seen wide adoption in enterprise-scale applications and is starting to be adopted in large-scale contexts. Training an AWE model has historically required a single batch of several hundred writing examples and human scores for each of them. This requirement limits large-scale adoption of AWE since human-scoring essays is costly. Here we evaluate algorithms for ensuring that AWE models are consistently trained using the most informative essays. Our results show how to minimize training set sizes while maximizing predictive performance, thereby reducing cost without unduly sacrificing accuracy. We conclude with a discussion of how to integrate this approach into large-scale AWE systems.
Gray Level Image Enhancement Using Polygonal Functions
Venue: arXiv cs.CV 2014
Year: 2014

This paper presents a method for enhancing the gray level images. This method takes part from the category of point transforms and it is based on interpolation functions. The latter have a graphic represented by polygonal lines. The interpolation nodes of these functions are calculated taking into account the statistics of gray levels belonging to the image.
Compression of high throughput sequencing data with probabilistic de Bruijn graph
Venue: arXiv cs.DS 2014
Year: 2014

Motivation: Data volumes generated by next-generation sequencing technolo- gies is now a major concern, both for storage and transmission. This triggered the need for more efficient methods than general purpose compression tools, such as the widely used gzip. Most reference-free tools developed for NGS data compression still use general text compression methods and fail to benefit from algorithms already designed specifically for the analysis of NGS data. The goal of our new method Leon is to achieve compression of DNA sequences of high throughput sequencing data, without the need of a reference genome, with techniques derived from existing assembly principles, that possibly better exploit NGS data redundancy. Results: We propose a novel method, implemented in the software Leon, for compression of DNA sequences issued from high throughput sequencing technologies. This is a lossless method that does not need a reference genome. Instead, a reference is built de novo from the set of reads as a probabilistic de Bruijn Graph, stored in a Bloom filter. Each read is encoded as a path in this graph, storing only an anchoring kmer and a list of bifurcations indicating which path to follow in the graph. This new method will allow to have compressed read files that also already contain its underlying de Bruijn Graph, thus directly re-usable by many tools relying on this structure. Leon achieved encoding of a C. elegans reads set with 0.7 bits/base, outperforming state of the art reference-free methods. Availability: Open source, under GNU affero GPL License, available for download at http://gatb.inria.fr/software/leon/
Large Scale Distributed Distance Metric Learning
Venue: arXiv cs.LG 2014
Year: 2014

In large scale machine learning and data mining problems with high feature dimensionality, the Euclidean distance between data points can be uninformative, and Distance Metric Learning (DML) is often desired to learn a proper similarity measure (using side information such as example data pairs being similar or dissimilar). However, high dimensionality and large volume of pairwise constraints in modern big data can lead to prohibitive computational cost for both the original DML formulation in Xing et al. (2002) and later extensions. In this paper, we present a distributed algorithm for DML, and a large-scale implementation on a parameter server architecture. Our approach builds on a parallelizable reformulation of Xing et al. (2002), and an asynchronous stochastic gradient descent optimization procedure. To our knowledge, this is the first distributed solution to DML, and we show that, on a system with 256 CPU cores, our program is able to complete a DML task on a dataset with 1 million data points, 22-thousand features, and 200 million labeled data pairs, in 15 hours; and the learned metric shows great effectiveness in properly measuring distances.
GraATP: A Graph Theoretic Approach for Automated Theorem Proving in Plane Geometry
Venue: arXiv cs.AI 2014
Year: 2014

Automated Theorem Proving (ATP) is an established branch of Artificial Intelligence. The purpose of ATP is to design a system which can automatically figure out an algorithm either to prove or disprove a mathematical claim, on the basis of a set of given premises, using a set of fundamental postulates and following the method of logical inference. In this paper, we propose GraATP, a generalized framework for automated theorem proving in plane geometry. Our proposed method translates the geometric entities into nodes of a graph and the relations between them as edges of that graph. The automated system searches for different ways to reach the conclusion for a claim via graph traversal by which the validity of the geometric theorem is examined.
Stochastic Local Search for Pattern Set Mining
Venue: arXiv cs.AI 2014
Year: 2014

Local search methods can quickly find good quality solutions in cases where systematic search methods might take a large amount of time. Moreover, in the context of pattern set mining, exhaustive search methods are not applicable due to the large search space they have to explore. In this paper, we propose the application of stochastic local search to solve the pattern set mining. Specifically, to the task of concept learning. We applied a number of local search algorithms on a standard benchmark instances for pattern set mining and the results show the potentials for further exploration.
CITlab ARGUS for historical data tables
Venue: arXiv cs.CV 2014
Year: 2014

We describe CITlab's recognition system for the ANWRESH-2014 competition attached to the 14. International Conference on Frontiers in Handwriting Recognition, ICFHR 2014. The task comprises word recognition from segmented historical documents. The core components of our system are based on multi-dimensional recurrent neural networks (MDRNN) and connectionist temporal classification (CTC). The software modules behind that as well as the basic utility technologies are essentially powered by PLANET's ARGUS framework for intelligent text recognition and image processing.