OpenRaiser/Intern-Atlas huggingface dataset:
Single-Solution Hypervolume Maximization and its use for Improving Generalization of Neural Networks
Venue: arXiv cs.LG 2016
Year: 2016

This paper introduces the hypervolume maximization with a single solution as an alternative to the mean loss minimization. The relationship between the two problems is proved through bounds on the cost function when an optimal solution to one of the problems is evaluated on the other, with a hyperparameter to control the similarity between the two problems. This same hyperparameter allows higher weight to be placed on samples with higher loss when computing the hypervolume's gradient, whose normalized version can range from the mean loss to the max loss. An experiment on MNIST with a neural network is used to validate the theory developed, showing that the hypervolume maximization can behave similarly to the mean loss minimization and can also provide better performance, resulting on a 20% reduction of the classification error on the test set.
Galois Correspondence on Linear Codes over Finite Chain Rings
Venue: arXiv cs.IT 2016
Year: 2016

Given $\texttt{S}|\texttt{R}$ a finite Galois extension of finite chain rings and $\mathcal{B}$ an $\texttt{S}$-linear code we define two Galois operators, the closure operator and the interior operator. We proof that a linear code is Galois invariant if and only if the row standard form of its generator matrix has all entries in the fixed ring by the Galois group and show a Galois correspondence in the class of $\texttt{S}$-linear codes. As applications some improvements of upper and lower bounds for the rank of the restriction and trace code are given and some applications to $\texttt{S}$-linear cyclic codes are shown.
Using Hadoop for Large Scale Analysis on Twitter: A Technical Report
Venue: arXiv cs.DB 2016
Year: 2016

Sentiment analysis (or opinion mining) on Twitter data has attracted much attention recently. One of the system's key features, is the immediacy in communication with other users in an easy, user-friendly and fast way. Consequently, people tend to express their feelings freely, which makes Twitter an ideal source for accumulating a vast amount of opinions towards a wide diversity of topics. This amount of information offers huge potential and can be harnessed to receive the sentiment tendency towards these topics. However, since none can invest an infinite amount of time to read through these tweets, an automated decision making approach is necessary. Nevertheless, most existing solutions are limited in centralized environments only. Thus, they can only process at most a few thousand tweets. Such a sample, is not representative to define the sentiment polarity towards a topic due to the massive number of tweets published daily. In this paper, we go one step further and develop a novel method for sentiment learning in the MapReduce framework. Our algorithm exploits the hashtags and emoticons inside a tweet, as sentiment labels, and proceeds to a classification procedure of diverse sentiment types in a parallel and distributed manner. Moreover, we utilize Bloom filters to compact the storage size of intermediate data and boost the performance of our algorithm. Through an extensive experimental evaluation, we prove that our solution is efficient, robust and scalable and confirm the quality of our sentiment identification.
Quantifying synergistic information using intermediate stochastic variables
Venue: arXiv cs.IT 2016
Year: 2016

Quantifying synergy among stochastic variables is an important open problem in information theory. Information synergy occurs when multiple sources together predict an outcome variable better than the sum of single-source predictions. It is an essential phenomenon in biology such as in neuronal networks and cellular regulatory processes, where different information flows integrate to produce a single response, but also in social cooperation processes as well as in statistical inference tasks in machine learning. Here we propose a metric of synergistic entropy and synergistic information from first principles. The proposed measure relies on so-called synergistic random variables (SRVs) which are constructed to have zero mutual information about individual source variables but non-zero mutual information about the complete set of source variables. We prove several basic and desired properties of our measure, including bounds and additivity properties. In addition, we prove several important consequences of our measure, including the fact that different types of synergistic information may co-exist between the same sets of variables. A numerical implementation is provided, which we use to demonstrate that synergy is associated with resilience to noise. Our measure may be a marked step forward in the study of multivariate information theory and its numerous applications.
Plurality Consensus via Shuffling: Lessons Learned from Load Balancing
Venue: arXiv cs.DS 2016
Year: 2016

We consider \emph{plurality consensus} in a network of $n$ nodes. Initially, each node has one of $k$ opinions. The nodes execute a (randomized) distributed protocol to agree on the plurality opinion (the opinion initially supported by the most nodes). Nodes in such networks are often quite cheap and simple, and hence one seeks protocols that are not only fast but also simple and space efficient. Typically, protocols depend heavily on the employed communication mechanism, which ranges from sequential (only one pair of nodes communicates at any time) to fully parallel (all nodes communicate with all their neighbors at once) communication and everything in-between. We propose a framework to design protocols for a multitude of communication mechanisms. We introduce protocols that solve the plurality consensus problem and are with probability 1-o(1) both time and space efficient. Our protocols are based on an interesting relationship between plurality consensus and distributed load balancing. This relationship allows us to design protocols that generalize the state of the art for a large range of problem parameters. In particular, we obtain the same bounds as the recent result of Alistarh et al. (who consider only two opinions on a clique) using a much simpler protocol that generalizes naturally to general graphs and multiple opinions.
Towards Scalable Synthesis of Stochastic Control Systems
Venue: arXiv cs.SY 2016
Year: 2016

Formal control synthesis approaches over stochastic systems have received significant attention in the past few years, in view of their ability to provide provably correct controllers for complex logical specifications in an automated fashion. Examples of complex specifications of interest include properties expressed as formulae in linear temporal logic (LTL) or as automata on infinite strings. A general methodology to synthesize controllers for such properties resorts to symbolic abstractions of the given stochastic systems. Symbolic models are discrete abstractions of the given concrete systems with the property that a controller designed on the abstraction can be refined (or implemented) into a controller on the original system. Although the recent development of techniques for the construction of symbolic models has been quite encouraging, the general goal of formal synthesis over stochastic control systems is by no means solved. A fundamental issue with the existing techniques is the known "curse of dimensionality," which is due to the need to discretize state and input sets and that results in an exponential complexity over the number of state and input variables in the concrete system. In this work we propose a novel abstraction technique for incrementally stable stochastic control systems, which does not require state-space discretization but only input set discretization, and that can be potentially more efficient (and thus scalable) than existing approaches. We elucidate the effectiveness of the proposed approach by synthesizing a schedule for the coordination of two traffic lights under some safety and fairness requirements for a road traffic model. Further we argue that this 5-dimensional linear stochastic control system cannot be studied with existing approaches based on state-space discretization due to the very large number of generated discrete states.
An SSD-based eigensolver for spectral analysis on billion-node graphs
Venue: arXiv cs.DC 2016
Year: 2016

Many eigensolvers such as ARPACK and Anasazi have been developed to compute eigenvalues of a large sparse matrix. These eigensolvers are limited by the capacity of RAM. They run in memory of a single machine for smaller eigenvalue problems and require the distributed memory for larger problems. In contrast, we develop an SSD-based eigensolver framework called FlashEigen, which extends Anasazi eigensolvers to SSDs, to compute eigenvalues of a graph with hundreds of millions or even billions of vertices in a single machine. FlashEigen performs sparse matrix multiplication in a semi-external memory fashion, i.e., we keep the sparse matrix on SSDs and the dense matrix in memory. We store the entire vector subspace on SSDs and reduce I/O to improve performance through caching the most recent dense matrix. Our result shows that FlashEigen is able to achieve 40%-60% performance of its in-memory implementation and has performance comparable to the Anasazi eigensolvers on a machine with 48 CPU cores. Furthermore, it is capable of scaling to a graph with 3.4 billion vertices and 129 billion edges. It takes about four hours to compute eight eigenvalues of the billion-node graph using 120 GB memory.
Online energy efficient packet scheduling for a common deadline with and without energy harvesting
Venue: arXiv cs.IT 2016
Year: 2016

The problem of online packet scheduling to minimize the required conventional grid energy for transmitting a fixed number of packets given a common deadline is considered. The total number of packets arriving within the deadline is known, but the packet arrival times are unknown, and can be arbitrary. The proposed algorithm tries to finish the transmission of each packet assuming all future packets are going to arrive at equal time intervals within the left-over time. The proposed online algorithm is shown to have competitive ratio that is logarithmic in the number of packet arrivals. The hybrid energy paradigm is also considered, where in addition to grid energy, energy is also available via extraction from renewable sources. The objective here is to minimize the grid energy use. A suitably modified version of the previous algorithm is also shown to have competitive ratio that is logarithmic in the number of packet arrivals.
Testing Wireless Sensor Networks with Hybrid Simulators
Venue: arXiv cs.NI 2016
Year: 2016

Software development for Wireless Sensor Networks (WSNs) is challenging due to characteristics of sensor nodes and the environment they are deployed in. Testing software in a real WSN testbed allows users to get reliable test results. However, real testbeds become more expensive as the number of sensor nodes in the network grows. Simulation tools are alternatives to real testbeds. They are cheaper, faster and repeatable. However, simulation results are not reliable as that of testbeds. Therefore, there is a need for a testing tool that can leverage the advantages of testbeds and simulation tools. These tools are usually called hybrid simulators. In this survey, we discuss several hybrid simulators that use real sensor motes integrated with a simulator to make software development cheaper, repeatable and to make the results more reliable.
Many Languages, One Parser
Venue: arXiv cs.CL 2016
Year: 2016

We train one multilingual model for dependency parsing and use it to parse sentences in several languages. The parsing model uses (i) multilingual word clusters and embeddings; (ii) token-level language information; and (iii) language-specific features (fine-grained POS tags). This input representation enables the parser not only to parse effectively in multiple languages, but also to generalize across languages based on linguistic universals and typological similarities, making it more effective to learn from limited annotations. Our parser's performance compares favorably to strong baselines in a range of data scenarios, including when the target language has a large treebank, a small treebank, or no treebank for training.
Connectivity of Cooperative Ad hoc Networks
Venue: arXiv cs.NI 2016
Year: 2016

The connectivity properties of ad hoc networks have been extensively studied over the past few years, from local observables, to global network properties. In this paper we introduce a novel layer of network dynamics which lives and evolves on top of the ad hoc network. Nodes are assumed selfish and a snow-drift type game is defined dictating the way nodes decide to allocate their cooperative resource efforts towards other nodes in the network. The dynamics are strongly coupled with the physical network causing the cooperation network topology to converge towards a stable equilibrium state, a global maximum of the total pay-off. We study this convergence from a connectivity perspective and analyse the inherent parameter dependence. Moreover, we show that direct reciprocity can be an efficient incentive to promote cooperation within the network and discuss the analogies between our simple yet tractable framework with D2D proximity based services such as LTE-Direct. We argue that cooperative network dynamics have many application in ICT, not just ad hoc networks, and similar models as the one described herein can be devised and studied in their own right.
Self-Transfer Learning for Fully Weakly Supervised Object Localization
Venue: arXiv cs.CV 2016
Year: 2016

Recent advances of deep learning have achieved remarkable performances in various challenging computer vision tasks. Especially in object localization, deep convolutional neural networks outperform traditional approaches based on extraction of data/task-driven features instead of hand-crafted features. Although location information of region-of-interests (ROIs) gives good prior for object localization, it requires heavy annotation efforts from human resources. Thus a weakly supervised framework for object localization is introduced. The term "weakly" means that this framework only uses image-level labeled datasets to train a network. With the help of transfer learning which adopts weight parameters of a pre-trained network, the weakly supervised learning framework for object localization performs well because the pre-trained network already has well-trained class-specific features. However, those approaches cannot be used for some applications which do not have pre-trained networks or well-localized large scale images. Medical image analysis is a representative among those applications because it is impossible to obtain such pre-trained networks. In this work, we present a "fully" weakly supervised framework for object localization ("semi"-weakly is the counterpart which uses pre-trained filters for weakly supervised localization) named as self-transfer learning (STL). It jointly optimizes both classification and localization networks simultaneously. By controlling a supervision level of the localization network, STL helps the localization network focus on correct ROIs without any types of priors. We evaluate the proposed STL framework using two medical image datasets, chest X-rays and mammograms, and achieve signiticantly better localization performance compared to previous weakly supervised approaches.
Formal Verification of Autonomous Vehicle Platooning
Venue: arXiv cs.AI 2016
Year: 2016

The coordination of multiple autonomous vehicles into convoys or platoons is expected on our highways in the near future. However, before such platoons can be deployed, the new autonomous behaviors of the vehicles in these platoons must be certified. An appropriate representation for vehicle platooning is as a multi-agent system in which each agent captures the "autonomous decisions" carried out by each vehicle. In order to ensure that these autonomous decision-making agents in vehicle platoons never violate safety requirements, we use formal verification. However, as the formal verification technique used to verify the agent code does not scale to the full system and as the global verification technique does not capture the essential verification of autonomous behavior, we use a combination of the two approaches. This mixed strategy allows us to verify safety requirements not only of a model of the system, but of the actual agent code used to program the autonomous vehicles.
Obtaining personal data and asking for erasure: Do app vendors and website owners honour your privacy rights?
Venue: arXiv cs.CY 2016
Year: 2016

EU Directive 95/46/EC and the upcoming EU General Data Protection Regulation grant Europeans the right of access to data pertaining to them. Consumers can approach their service providers to obtain all personal data stored and processed there. Furthermore, they can demand erasure (or correction) of their data. We conducted an undercover field study to determine whether these rights can be exerted in practice. We assessed the behaviour of the vendors of 150 smartphone apps and 120 websites that are popular in Germany. Our deletion requests were fulfilled in 52 to 57% of the cases and less than half of the data provision requests were answered satisfactorily. Further, we observed instances of carelessness: About 20% of website owners would have disclosed our personal data to impostors. The results indicate that exerting privacy rights that have been introduced two decades ago is still a frustrating endeavour most of the time.
Search Tracker: Human-derived object tracking in-the-wild through large-scale search and retrieval
Venue: arXiv cs.CV 2016
Year: 2016

Humans use context and scene knowledge to easily localize moving objects in conditions of complex illumination changes, scene clutter and occlusions. In this paper, we present a method to leverage human knowledge in the form of annotated video libraries in a novel search and retrieval based setting to track objects in unseen video sequences. For every video sequence, a document that represents motion information is generated. Documents of the unseen video are queried against the library at multiple scales to find videos with similar motion characteristics. This provides us with coarse localization of objects in the unseen video. We further adapt these retrieved object locations to the new video using an efficient warping scheme. The proposed method is validated on in-the-wild video surveillance datasets where we outperform state-of-the-art appearance-based trackers. We also introduce a new challenging dataset with complex object appearance changes.
Effective Clipart Image Vectorization Through Direct Optimization of Bezigons
Venue: arXiv cs.GR 2016
Year: 2016

Bezigons, i.e., closed paths composed of Bézier curves, have been widely employed to describe shapes in image vectorization results. However, most existing vectorization techniques infer the bezigons by simply approximating an intermediate vector representation (such as polygons). Consequently, the resultant bezigons are sometimes imperfect due to accumulated errors, fitting ambiguities, and a lack of curve priors, especially for low-resolution images. In this paper, we describe a novel method for vectorizing clipart images. In contrast to previous methods, we directly optimize the bezigons rather than using other intermediate representations; therefore, the resultant bezigons are not only of higher fidelity compared with the original raster image but also more reasonable because they were traced by a proficient expert. To enable such optimization, we have overcome several challenges and have devised a differentiable data energy as well as several curve-based prior terms. To improve the efficiency of the optimization, we also take advantage of the local control property of bezigons and adopt an overlapped piecewise optimization strategy. The experimental results show that our method outperforms both the current state-of-the-art method and commonly used commercial software in terms of bezigon quality.
Investigating Reliability Aspects of Memristor based RRAM with Reference to Write Voltage and Frequency
Venue: arXiv cs.ET 2016
Year: 2016

In this paper, we report the effect of write voltage and frequency on memristor based Resistive Random Access Memory (RRAM). The above said parameters have been investigated on the linear drift model of memristor. With a variation of write voltage from 0.2V to 1.2V and a subsequent frequency modulation from 1, 2, 4, 10, 100 and 200 Hz the corresponding effects on memory window, Low Resistance State (LRS) and High Resistance State (HRS) have been reported. Thus the lifetime (τ) reliability analysis of memristor based RRAM is carried out using above results. It is found that, the HRS is independent of write voltage, whereas LRS shows dependency on write voltage and frequency. The simulation results showcase that the memristor possess higher memory window and lifetime (τ) in the higher voltage with lower frequency region, which has been attributed to the fewer data losses in the memory architecture.
Lifetime-Based Memory Management for Distributed Data Processing Systems
Venue: arXiv cs.DC 2016
Year: 2016

In-memory caching of intermediate data and eager combining of data in shuffle buffers have been shown to be very effective in minimizing the re-computation and I/O cost in distributed data processing systems like Spark and Flink. However, it has also been widely reported that these techniques would create a large amount of long-living data objects in the heap, which may quickly saturate the garbage collector, especially when handling a large dataset, and hence would limit the scalability of the system. To eliminate this problem, we propose a lifetime-based memory management framework, which, by automatically analyzing the user-defined functions and data types, obtains the expected lifetime of the data objects, and then allocates and releases memory space accordingly to minimize the garbage collection overhead. In particular, we present Deca, a concrete implementation of our proposal on top of Spark, which transparently decomposes and groups objects with similar lifetimes into byte arrays and releases their space altogether when their lifetimes come to an end. An extensive experimental study using both synthetic and real datasets shows that, in comparing to Spark, Deca is able to 1) reduce the garbage collection time by up to 99.9%, 2) to achieve up to 22.7x speed up in terms of execution time in cases without data spilling and 41.6x speedup in cases with data spilling, and 3) to consume up to 46.6% less memory.
Winning Cores in Parity Games
Venue: arXiv cs.GT 2016
Year: 2016

We introduce the novel notion of winning cores in parity games and develop a deterministic polynomial-time under-approximation algorithm for solving parity games based on winning core approximation. Underlying this algorithm are a number properties about winning cores which are interesting in their own right. In particular, we show that the winning core and the winning region for a player in a parity game are equivalently empty. Moreover, the winning core contains all fatal attractors but is not necessarily a dominion itself. Experimental results are very positive both with respect to quality of approximation and running time. It outperforms existing state-of-the-art algorithms significantly on most benchmarks.