OpenRaiser/Intern-Atlas huggingface dataset:
What does mathoverflow tell us about the production of mathematics?
Venue: arXiv cs.SI 2013
Year: 2013

The highest level of mathematics research is traditionally seen as a solitary activity. Yet new innovations by mathematicians themselves are starting to harness the power of social computation to create new modes of mathematical production. We study the effectiveness of one such system, and make proposals for enhancement, drawing on AI and computer based mathematics. We analyse the content of a sample of questions and responses in the community question answering system for research mathematicians, math-overflow. We find that mathoverflow is very effective, with 90% of our sample of questions answered completely or in part. A typical response is an informal dialogue, allowing error and speculation, rather than rigorous mathematical argument: 37% of our sample discussions acknowledged error. Responses typically present information known to the respondent, and readily checked by other users: thus the effectiveness of mathoverflow comes from information sharing. We conclude that extending and the power and reach of mathoverflow through a combination of people and machines raises new challenges for artificial intelligence and computational mathematics, in particular how to handle error, analogy and informal reasoning.
Time-Reversible Random Number Generators : Solution of Our Challenge by Federico Ricci-Tersenghi
Venue: arXiv cs.DM 2013
Year: 2013

Nearly all the evolution equations of physics are time-reversible, in the sense that a movie of the solution, played backwards, would obey exactly the same differential equations as the original forward solution. By way of contrast, stochastic approaches are typically not time-reversible, though they could be made so by the simple expedient of storing their underlying pseudorandom numbers in an array. Here we illustrate the notion of time-reversible random number generators. In Version 1 we offered a suitable reward for the first arXiv response furnishing a reversed version of an only slightly-more-complicated pseudorandom number generator. Here we include Professor Ricci-Tersenghi's prize-winning reversed version as described in his arXiv:1305.1805 contribution: "The Solution to the Challenge in `Time-Reversible Random Number Generators' by Wm. G. Hoover and Carol G. Hoover".
Incremental Sampling-based Algorithm for Minimum-violation Motion Planning
Venue: arXiv cs.RO 2013
Year: 2013

This paper studies the problem of control strategy synthesis for dynamical systems with differential constraints to fulfill a given reachability goal while satisfying a set of safety rules. Particular attention is devoted to goals that become feasible only if a subset of the safety rules are violated. The proposed algorithm computes a control law, that minimizes the level of unsafety while the desired goal is guaranteed to be reached. This problem is motivated by an autonomous car navigating an urban environment while following rules of the road such as "always travel in right lane'' and "do not change lanes frequently''. Ideas behind sampling based motion-planning algorithms, such as Probabilistic Road Maps (PRMs) and Rapidly-exploring Random Trees (RRTs), are employed to incrementally construct a finite concretization of the dynamics as a durational Kripke structure. In conjunction with this, a weighted finite automaton that captures the safety rules is used in order to find an optimal trajectory that minimizes the violation of safety rules. We prove that the proposed algorithm guarantees asymptotic optimality, i.e., almost-sure convergence to optimal solutions. We present results of simulation experiments and an implementation on an autonomous urban mobility-on-demand system.
Acoustic Echo Cancellation Postfilter Design Issues For Speech Recognition System
Venue: arXiv cs.SD 2013
Year: 2013

In this paper a generalized postfilter algorithm design issues are presented. This postfilter is used to jointly suppress late reverberation, residual echo, and background noise. When residual echo and noise are suppressed, the best result obtains by suppressing both interferences together after the Acoustic echo cancellation (AEC). The main advantage of this approach is that the residual echo and noise suppression does not suffer from the existence of a strong acoustic echo component. Furthermore, the Acoustic echo cancellation (AEC) does not suffer from the time-varying noise suppression. A disadvantage is that the input signal of the Acoustic echo cancellation (AEC) has a low signal-to-noise ratio (SNR). To overcome this problem, algorithms have been proposed where, apart from the joint suppression, a noise-reduced signal is used to adapt the echo canceller.
Gromov-Hausdorff Approximation of Metric Spaces with Linear Structure
Venue: arXiv cs.CG 2013
Year: 2013

In many real-world applications data come as discrete metric spaces sampled around 1-dimensional filamentary structures that can be seen as metric graphs. In this paper we address the metric reconstruction problem of such filamentary structures from data sampled around them. We prove that they can be approximated, with respect to the Gromov-Hausdorff distance by well-chosen Reeb graphs (and some of their variants) and we provide an efficient and easy to implement algorithm to compute such approximations in almost linear time. We illustrate the performances of our algorithm on a few synthetic and real data sets.
A Contrario Selection of Optimal Partitions for Image Segmentation
Venue: arXiv cs.CV 2013
Year: 2013

We present a novel segmentation algorithm based on a hierarchical representation of images. The main contribution of this work is to explore the capabilities of the A Contrario reasoning when applied to the segmentation problem, and to overcome the limitations of current algorithms within that framework. This exploratory approach has three main goals. Our first goal is to extend the search space of greedy merging algorithms to the set of all partitions spanned by a certain hierarchy, and to cast the segmentation as a selection problem within this space. In this way we increase the number of tested partitions and thus we potentially improve the segmentation results. In addition, this space is considerably smaller than the space of all possible partitions, thus we still keep the complexity controlled. Our second goal aims to improve the locality of region merging algorithms, which usually merge pairs of neighboring regions. In this work, we overcome this limitation by introducing a validation procedure for complete partitions, rather than for pairs of regions. The third goal is to perform an exhaustive experimental evaluation methodology in order to provide reproducible results. Finally, we embed the selection process on a statistical A Contrario framework which allows us to have only one free parameter related to the desired scale.
Construction of two SD Codes
Venue: arXiv cs.IT 2013
Year: 2013

SD codes are erasure codes that address the mixed failure mode of current RAID systems. Rather than dedicate entire disks to erasure coding, as done in RAID-5, RAID-6 and Reed-Solomon coding, an SD code dedicates entire disks, plus individual sectors to erasure coding. The code then tolerates combinations of disk and sector errors, rather than solely disk errors. It is been an open problem to construct general codes that have the SD property, and previous work has relied on Monte Carlo searches. In this paper, we present two general constructions that address the cases with one disk and two sectors, and two disks and two sectors. Additionally, we make an observation about shortening SD codes that allows us to prune Monte Carlo searches.
Design and Implementation of a Wireless Sensor and Actuator Network for Energy Measurement and Control at Home
Venue: arXiv cs.NI 2013
Year: 2013

This paper describes the design, implementation, and testing of a wireless sensor and actuator network for monitoring the energy use of electric appliances in a home environment. The network includes energy measurement nodes and a central server, where the nodes read the energy use of connected appliance, and wirelessly report their readings to the central server for processing. The server displays the readings from these nodes via a user visual interface in real time. Through this system, users can easily understand their electricity usage patterns and adapt their behavior to reduce their energy consumption and costs. Moreover, users are able to remotely power on/off individual devices to actively control the power use of certain appliances. The system allows for inexpensive monitoring of home energy use and illustrates a practical way to control the energy consumption through user interaction.
Towards an Author-Topic-Term-Model Visualization of 100 Years of German Sociological Society Proceedings
Venue: arXiv cs.DL 2013
Year: 2013

Author co-citation studies employ factor analysis to reduce high-dimensional co-citation matrices to low-dimensional and possibly interpretable factors, but these studies do not use any information from the text bodies of publications. We hypothesise that term frequencies may yield useful information for scientometric analysis. In our work we ask if word features in combination with Bayesian analysis allow well-founded science mapping studies. This work goes back to the roots of Mosteller and Wallace's (1964) statistical text analysis using word frequency features and a Bayesian inference approach, tough with different goals. To answer our research question we (i) introduce a new data set on which the experiments are carried out, (ii) describe the Bayesian model employed for inference and (iii) present first results of the analysis.
Supervision Localization of Timed Discrete-Event Systems
Venue: arXiv cs.SY 2013
Year: 2013

We study supervisor localization for real-time discrete-event systems (DES) in the Brandin-Wonham framework of timed supervisory control. We view a real-time DES as comprised of asynchronous agents which are coupled through imposed logical and temporal specifications; the essence of supervisor localization is the decomposition of monolithic (global) control action into local control strategies for these individual agents. This study extends our previous work on supervisor localization for untimed DES, in that monolithic timed control action typically includes not only disabling action as in the untimed case, but also ``clock preempting'' action which enforces prescribed temporal behavior. The latter action is executed by a class of special events, called ``forcible'' events; accordingly, we localize monolithic preemptive action with respect to these events. We demonstrate the new features of timed supervisor localization with a manufacturing cell case study, and discuss a distributed control implementation.
Generalised Sphere Decoding for Spatial Modulation
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, Sphere Decoding (SD) algorithms for Spatial Modulation (SM) are developed to reduce the computational complexity of Maximum-Likelihood (ML) detectors. Two SDs specifically designed for SM are proposed and analysed in terms of Bit Error Ratio (BER) and computational complexity. Using Monte Carlo simulations and mathematical analysis, it is shown that by carefully choosing the initial radius the proposed sphere decoder algorithms offer the same BER as ML detection, with a significant reduction in the computational complexity. A tight closed form expression for the BER performance of SM-SD is derived in the paper, along with an algorithm for choosing the initial radius which provides near to optimum performance. Also, it is shown that none of the proposed SDs are always superior to the others, but the best SD to use depends on the target spectral efficiency. The computational complexity trade-off offered by the proposed solutions is studied via analysis and simulation, and is shown to validate our findings. Finally, the performance of SM-SDs are compared to Spatial Multiplexing (SMX) applying ML decoder and applying SD. It is shown that for the same spectral efficiency, SM-SD offers up to 84% reduction in complexity compared to SMX-SD, with up to 1 dB better BER performance than SMX-ML decoder.
Formal Representation of the SS-DB Benchmark and Experimental Evaluation in EXTASCID
Venue: arXiv cs.DB 2013
Year: 2013

Evaluating the performance of scientific data processing systems is a difficult task considering the plethora of application-specific solutions available in this landscape and the lack of a generally-accepted benchmark. The dual structure of scientific data coupled with the complex nature of processing complicate the evaluation procedure further. SS-DB is the first attempt to define a general benchmark for complex scientific processing over raw and derived data. It fails to draw sufficient attention though because of the ambiguous plain language specification and the extraordinary SciDB results. In this paper, we remedy the shortcomings of the original SS-DB specification by providing a formal representation in terms of ArrayQL algebra operators and ArrayQL/SciQL constructs. These are the first formal representations of the SS-DB benchmark. Starting from the formal representation, we give a reference implementation and present benchmark results in EXTASCID, a novel system for scientific data processing. EXTASCID is complete in providing native support both for array and relational data and extensible in executing any user code inside the system by the means of a configurable metaoperator. These features result in an order of magnitude improvement over SciDB at data loading, extracting derived data, and operations over derived data.
Vers une Substitution des Services Web sans Inconsistance Sémantique
Venue: arXiv cs.SE 2013
Year: 2013

In order to ensure high availability of Web services, recently, a new approach was proposed based on the use of communities. In composition, this approach consists in replacing the failed Web service by another web service joining a community offering the same functionality of the service failed. However, this substitution may cause inconsistency in the semantic composition and alter its mediation initially taken to resolve the semantic heterogeneities between Web services. This paper presents a context oriented solution to this problem by forcing the community to adopt the semantic of the failed web service before the substitution in which all inputs and outputs to/from the latter must be converted according to this adopted semantic, avoiding any alteration of a semantic mediation in web service composition.
Class Imbalance Problem in Data Mining Review
Venue: arXiv cs.LG 2013
Year: 2013

In last few years there are major changes and evolution has been done on classification of data. As the application area of technology is increases the size of data also increases. Classification of data becomes difficult because of unbounded size and imbalance nature of data. Class imbalance problem become greatest issue in data mining. Imbalance problem occur where one of the two classes having more sample than other classes. The most of algorithm are more focusing on classification of major sample while ignoring or misclassifying minority sample. The minority samples are those that rarely occur but very important. There are different methods available for classification of imbalance data set which is divided into three main categories, the algorithmic approach, data-preprocessing approach and feature selection approach. Each of this technique has their own advantages and disadvantages. In this paper systematic study of each approach is define which gives the right direction for research in class imbalance problem.
When Politicians Tweet: A Study on the Members of the German Federal Diet
Venue: arXiv cs.SI 2013
Year: 2013

In this preliminary study we compare the characteristics of retweets and replies on more than 350,000 messages collected by following members of the German Federal Diet on Twitter. We find significant differences in the characteristics pointing to distinct types of usages for retweets and replies. Using time series and regression analysis we observe that the likelihood of a politician using replies increases with typical leisure times while retweets occur constant over time. Including formal references increases the probability of a message being retweeted but drops its chance of being replied. This hints to a more professional use for retweets while replies tend to have a personal connotation.
Improving Diffusion-Based Molecular Communication with Unanchored Enzymes
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we propose adding enzymes to the propagation environment of a diffusive molecular communication system as a strategy for mitigating intersymbol interference. The enzymes form reaction intermediates with information molecules and then degrade them so that they have a smaller chance of interfering with future transmissions. We present the reaction-diffusion dynamics of this proposed system and derive a lower bound expression for the expected number of molecules observed at the receiver. We justify a particle-based simulation framework, and present simulation results that show both the accuracy of our expression and the potential for enzymes to improve communication performance.
An Architecture for Decentralised Orchestration of Web Service Workflows
Venue: arXiv cs.DC 2013
Year: 2013

Service-oriented workflows are typically executed using a centralised orchestration approach that presents significant scalability challenges. These challenges include the consumption of network bandwidth, degradation of performance, and single-points of failure. We provide a decentralised orchestration architecture that attempts to address these challenges. Our architecture adopts a design model that permits the computation to be moved "closer" to services in a workflow. This is achieved by partitioning workflows specified using our simple dataflow language into smaller fragments, which may be sent to remote locations for execution.
Residue Classes of the PPT Sequence
Venue: arXiv cs.CR 2013
Year: 2013

Primitive Pythagorean triples (PPT) may be put into different equivalence classes using residues with respect to primes. We show that the probability that the smaller odd number associated with the PPT triple is divisible by prime p is 2/(p+1). We have determined the autocorrelation function of the Baudhayana sequences obtained from the residue classes and we show these sequences have excellent randomness properties. We provide analytical explanation for the peak and the average off-peak values for the autocorrelation function. These sequences can be used specifically in a variety of key generation and distribution problems and, more generally, as pseudorandom sequences.
Improving Receiver Performance of Diffusive Molecular Communication with Enzymes
Venue: arXiv cs.IT 2013
Year: 2013

This paper studies the mitigation of intersymbol interference in a diffusive molecular communication system using enzymes that freely diffuse in the propagation environment. The enzymes form reaction intermediates with information molecules and then degrade them so that they cannot interfere with future transmissions. A lower bound expression on the expected number of molecules measured at the receiver is derived. A simple binary receiver detection scheme is proposed where the number of observed molecules is sampled at the time when the maximum number of molecules is expected. Insight is also provided into the selection of an appropriate bit interval. The expected bit error probability is derived as a function of the current and all previously transmitted bits. Simulation results show the accuracy of the bit error probability expression and the improvement in communication performance by having active enzymes present.
Stochastic gradient descent algorithms for strongly convex functions at O(1/T) convergence rates
Venue: arXiv cs.LG 2013
Year: 2013

With a weighting scheme proportional to t, a traditional stochastic gradient descent (SGD) algorithm achieves a high probability convergence rate of O(κ/T) for strongly convex functions, instead of O(κ ln(T)/T). We also prove that an accelerated SGD algorithm also achieves a rate of O(κ/T).
The effects of computer assisted and distance learning of geometric modelling
Venue: arXiv cs.CY 2013
Year: 2013

The effects of computer-assisted and distance learning of geometric modeling and computer aided geometric design are studied. It was shown that computer algebra systems and dynamic geometric environments can be considered as excellent tools for teaching mathematical concepts of mentioned areas, and distance education technologies would be indispensable for consolidation of successfully passed topics.
Rate Region of the (4,3,3) Exact-Repair Regenerating Codes
Venue: arXiv cs.IT 2013
Year: 2013

Exact-repair regenerating codes are considered for the case (n,k,d)=(4,3,3), for which a complete characterization of the rate region is provided. This characterization answers in the affirmative the open question whether there exists a non-vanishing gap between the optimal bandwidth-storage tradeoff of the functional-repair regenerating codes (i.e., the cut-set bound) and that of the exact-repair regenerating codes. The converse proof relies on the existence of symmetric optimal solutions. For the achievability, only one non-trivial corner point of the rate region needs to be addressed, for which an explicit binary code construction is given.
Geiringer Theorems: From Population Genetics to Computational Intelligence, Memory Evolutive Systems and Hebbian Learning
Venue: arXiv cs.NE 2013
Year: 2013

The classical Geiringer theorem addresses the limiting frequency of occurrence of various alleles after repeated application of crossover. It has been adopted to the setting of evolutionary algorithms and, a lot more recently, reinforcement learning and Monte-Carlo tree search methodology to cope with a rather challenging question of action evaluation at the chance nodes. The theorem motivates novel dynamic parallel algorithms that are explicitly described in the current paper for the first time. The algorithms involve independent agents traversing a dynamically constructed directed graph that possibly has loops. A rather elegant and profound category-theoretic model of cognition in biological neural networks developed by a well-known French mathematician, professor Andree Ehresmann jointly with a neurosurgeon, Jan Paul Vanbremeersch over the last thirty years provides a hint at the connection between such algorithms and Hebbian learning.
Practical Fine-grained Privilege Separation in Multithreaded Applications
Venue: arXiv cs.OS 2013
Year: 2013

An inherent security limitation with the classic multithreaded programming model is that all the threads share the same address space and, therefore, are implicitly assumed to be mutually trusted. This assumption, however, does not take into consideration of many modern multithreaded applications that involve multiple principals which do not fully trust each other. It remains challenging to retrofit the classic multithreaded programming model so that the security and privilege separation in multi-principal applications can be resolved. This paper proposes ARBITER, a run-time system and a set of security primitives, aimed at fine-grained and data-centric privilege separation in multithreaded applications. While enforcing effective isolation among principals, ARBITER still allows flexible sharing and communication between threads so that the multithreaded programming paradigm can be preserved. To realize controlled sharing in a fine-grained manner, we created a novel abstraction named ARBITER Secure Memory Segment (ASMS) and corresponding OS support. Programmers express security policies by labeling data and principals via ARBITER's API following a unified model. We ported a widely-used, in-memory database application (memcached) to ARBITER system, changing only around 100 LOC. Experiments indicate that only an average runtime overhead of 5.6% is induced to this security enhanced version of application.