OpenRaiser/Intern-Atlas huggingface dataset:
Using the WOWA operator in robust discrete optimization problems
Venue: arXiv cs.DS 2015
Year: 2015

In this paper a class of discrete optimization problems with uncertain costs is discussed. The uncertainty is modeled by introducing a scenario set containing a finite number of cost scenarios. A probability distribution in the scenario set is available. In order to choose a solution the weighted OWA criterion (WOWA) is applied. This criterion allows decision makers to take into account both probabilities for scenarios and the degree of pessimism/ optimism. In this paper the complexity of the considered class of discrete optimization problems is described and some exact and approximation algorithms for solving it are proposed. An application to a selection problem, together with results of computational tests are shown.
Prefix-Projection Global Constraint for Sequential Pattern Mining
Venue: arXiv cs.AI 2015
Year: 2015

Sequential pattern mining under constraints is a challenging data mining task. Many efficient ad hoc methods have been developed for mining sequential patterns, but they are all suffering from a lack of genericity. Recent works have investigated Constraint Programming (CP) methods, but they are not still effective because of their encoding. In this paper, we propose a global constraint based on the projected databases principle which remedies to this drawback. Experiments show that our approach clearly outperforms CP approaches and competes well with ad hoc methods on large datasets.
Efficient Lipschitz Extensions for High-Dimensional Graph Statistics and Node Private Degree Distributions
Venue: arXiv cs.CR 2015
Year: 2015

Lipschitz extensions were recently proposed as a tool for designing node differentially private algorithms. However, efficiently computable Lipschitz extensions were known only for 1-dimensional functions (that is, functions that output a single real value). In this paper, we study efficiently computable Lipschitz extensions for multi-dimensional (that is, vector-valued) functions on graphs. We show that, unlike for 1-dimensional functions, Lipschitz extensions of higher-dimensional functions on graphs do not always exist, even with a non-unit stretch. We design Lipschitz extensions with small stretch for the sorted degree list and for the degree distribution of a graph. Crucially, our extensions are efficiently computable. We also develop new tools for employing Lipschitz extensions in the design of differentially private algorithms. Specifically, we generalize the exponential mechanism, a widely used tool in data privacy. The exponential mechanism is given a collection of score functions that map datasets to real values. It attempts to return the name of the function with nearly minimum value on the data set. Our generalized exponential mechanism provides better accuracy when the sensitivity of an optimal score function is much smaller than the maximum sensitivity of score functions. We use our Lipschitz extension and the generalized exponential mechanism to design a node-differentially private algorithm for releasing an approximation to the degree distribution of a graph. Our algorithm is much more accurate than algorithms from previous work.
Hardware based Scale- and Rotation-Invariant Feature Extraction: A Retrospective Analysis and Future Directions
Venue: arXiv cs.CV 2015
Year: 2015

Computer Vision techniques represent a class of algorithms that are highly computation and data intensive in nature. Generally, performance of these algorithms in terms of execution speed on desktop computers is far from real-time. Since real-time performance is desirable in many applications, special-purpose hardware is required in most cases to achieve this goal. Scale- and rotation-invariant local feature extraction is a low level computer vision task with very high computational complexity. The state-of-the-art algorithms that currently exist in this domain, like SIFT and SURF, suffer from slow execution speeds and at best can only achieve rates of 2-3 Hz on modern desktop computers. Hardware-based scale- and rotation-invariant local feature extraction is an emerging trend enabling real-time performance for these computationally complex algorithms. This paper takes a retrospective look at the advances made so far in this field, discusses the hardware design strategies employed and results achieved, identifies current research gaps and suggests future research directions.
Who Spoke What? A Latent Variable Framework for the Joint Decoding of Multiple Speakers and their Keywords
Venue: arXiv cs.SD 2015
Year: 2015

In this paper, we present a latent variable (LV) framework to identify all the speakers and their keywords given a multi-speaker mixture signal. We introduce two separate LVs to denote active speakers and the keywords uttered. The dependency of a spoken keyword on the speaker is modeled through a conditional probability mass function. The distribution of the mixture signal is expressed in terms of the LV mass functions and speaker-specific-keyword models. The proposed framework admits stochastic models, representing the probability density function of the observation vectors given that a particular speaker uttered a specific keyword, as speaker-specific-keyword models. The LV mass functions are estimated in a Maximum Likelihood framework using the Expectation Maximization (EM) algorithm. The active speakers and their keywords are detected as modes of the joint distribution of the two LVs. In mixture signals, containing two speakers uttering the keywords simultaneously, the proposed framework achieves an accuracy of 82% for detecting both the speakers and their respective keywords, using Student's-t mixture models as speaker-specific-keyword models.
The ELAPS Framework: Experimental Linear Algebra Performance Studies
Venue: arXiv cs.PF 2015
Year: 2015

Optimal use of computing resources requires extensive coding, tuning and benchmarking. To boost developer productivity in these time consuming tasks, we introduce the Experimental Linear Algebra Performance Studies framework (ELAPS), a multi-platform open source environment for fast yet powerful performance experimentation with dense linear algebra kernels, algorithms, and libraries. ELAPS allows users to construct experiments to investigate how performance and efficiency vary depending on factors such as caching, algorithmic parameters, problem size, and parallelism. Experiments are designed either through Python scripts or a specialized GUI, and run on the whole spectrum of architectures, ranging from laptops to clusters, accelerators, and supercomputers. The resulting experiment reports provide various metrics and statistics that can be analyzed both numerically and visually. We demonstrate the use of ELAPS in four concrete application scenarios and in as many computing environments, illustrating its practical value in supporting critical performance decisions.
Model Selection and Overfitting in Genetic Programming: Empirical Study [Extended Version]
Venue: arXiv cs.NE 2015
Year: 2015

Genetic Programming has been very successful in solving a large area of problems but its use as a machine learning algorithm has been limited so far. One of the reasons is the problem of overfitting which cannot be solved or suppresed as easily as in more traditional approaches. Another problem, closely related to overfitting, is the selection of the final model from the population. In this article we present our research that addresses both problems: overfitting and model selection. We compare several ways of dealing with ovefitting, based on Random Sampling Technique (RST) and on using a validation set, all with an emphasis on model selection. We subject each approach to a thorough testing on artificial and real--world datasets and compare them with the standard approach, which uses the full training data, as a baseline.
Noise Sensitivity of Teager-Kaiser Energy Operators and Their Ratios
Venue: arXiv cs.SD 2015
Year: 2015

The Teager-Kaiser energy operator (TKO) belongs to a class of autocorrelators and their linear combination that can track the instantaneous energy of a nonstationary sinusoidal signal source. TKO-based monocomponent AM-FM demodulation algorithms work under the basic assumption that the operator outputs are always positive. In the absence of noise, this is assured for pure sinusoidal inputs and the instantaneous property is also guaranteed. Noise invalidates both of these, particularly under small signal conditions. Post-detection filtering and thresholding are of use to reestablish these at the cost of some time to acquire. Key questions are: (a) how many samples must one use and (b) how much noise power at the detector input can one tolerate. Results of study of the role of delay and the limits imposed by additive Gaussian noise are presented along with the computation of the cumulants and probability density functions of the individual quadratic forms and their ratios.
Hierarchical Subquery Evaluation for Active Learning on a Graph
Venue: arXiv cs.CV 2015
Year: 2015

To train good supervised and semi-supervised object classifiers, it is critical that we not waste the time of the human experts who are providing the training labels. Existing active learning strategies can have uneven performance, being efficient on some datasets but wasteful on others, or inconsistent just between runs on the same dataset. We propose perplexity based graph construction and a new hierarchical subquery evaluation algorithm to combat this variability, and to release the potential of Expected Error Reduction. Under some specific circumstances, Expected Error Reduction has been one of the strongest-performing informativeness criteria for active learning. Until now, it has also been prohibitively costly to compute for sizeable datasets. We demonstrate our highly practical algorithm, comparing it to other active learning measures on classification datasets that vary in sparsity, dimensionality, and size. Our algorithm is consistent over multiple runs and achieves high accuracy, while querying the human expert for labels at a frequency that matches their desired time budget.
Explanation of Stagnation at Points that are not Local Optima in Particle Swarm Optimization by Potential Analysis
Venue: arXiv cs.AI 2015
Year: 2015

Particle Swarm Optimization (PSO) is a nature-inspired meta-heuristic for solving continuous optimization problems. In the literature, the potential of the particles of swarm has been used to show that slightly modified PSO guarantees convergence to local optima. Here we show that under specific circumstances the unmodified PSO, even with swarm parameters known (from the literature) to be good, almost surely does not yield convergence to a local optimum is provided. This undesirable phenomenon is called stagnation. For this purpose, the particles' potential in each dimension is analyzed mathematically. Additionally, some reasonable assumptions on the behavior if the particles' potential are made. Depending on the objective function and, interestingly, the number of particles, the potential in some dimensions may decrease much faster than in other dimensions. Therefore, these dimensions lose relevance, i.e., the contribution of their entries to the decisions about attractor updates becomes insignificant and, with positive probability, they never regain relevance. If Brownian Motion is assumed to be an approximation of the time-dependent drop of potential, practical, i.e., large values for this probability are calculated. Finally, on chosen multidimensional polynomials of degree two, experiments are provided showing that the required circumstances occur quite frequently. Furthermore, experiments are provided showing that even when the very simple sphere function is processed the described stagnation phenomenon occurs. Consequently, unmodified PSO does not converge to any local optimum of the chosen functions for tested parameter settings.
Cellular-Broadcast Service Convergence through Caching for CoMP Cloud RANs
Venue: arXiv cs.IT 2015
Year: 2015

Cellular and Broadcast services have been traditionally treated independently due to the different market requirements, thus resulting in different business models and orthogonal frequency allocations. However, with the advent of cheap memory and smart caching, this traditional paradigm can converge into a single system which can provide both services in an efficient manner. This paper focuses on multimedia delivery through an integrated network, including both a cellular (also known as unicast or broadband) and a broadcast last mile operating over shared spectrum. The subscribers of the network are equipped with a cache which can effectively create zero perceived latency for multimedia delivery, assuming that the content has been proactively and intelligently cached. The main objective of this work is to establish analytically the optimal content popularity threshold, based on a intuitive cost function. In other words, the aim is to derive which content should be broadcasted and which content should be unicasted. To facilitate this, Cooperative Multi- Point (CoMP) joint processing algorithms are employed for the uni and broad-cast PHY transmissions. To practically implement this, the integrated network controller is assumed to have access to traffic statistics in terms of content popularity. Simulation results are provided to assess the gain in terms of total spectral efficiency. A conventional system, where the two networks operate independently, is used as benchmark.
MORPH: A Reference Architecture for Configuration and Behaviour Self-Adaptation
Venue: arXiv cs.SE 2015
Year: 2015

An architectural approach to self-adaptive systems involves runtime change of system configuration (i.e., the system's components, their bindings and operational parameters) and behaviour update (i.e., component orchestration). Thus, dynamic reconfiguration and discrete event control theory are at the heart of architectural adaptation. Although controlling configuration and behaviour at runtime has been discussed and applied to architectural adaptation, architectures for self-adaptive systems often compound these two aspects reducing the potential for adaptability. In this paper we propose a reference architecture that allows for coordinated yet transparent and independent adaptation of system configuration and behaviour.
Another look in the Analysis of Cooperative Spectrum Sensing over Nakagami-$m$ Fading Channels
Venue: arXiv cs.IT 2015
Year: 2015

Modeling and analysis of cooperative spectrum sensing is an important aspect in cognitive radio systems. In this paper, the problem of energy detection (ED) of an unknown signal over Nakagami-$m$ fading is revisited. Specifically, an analytical expression for the local probability of detection is derived, while using the approach of ED at the individual secondary user (SU), a new fusion rule, based on the likelihood ratio test, is presented. The channels between the primary user to SUs and SUs to fusion center are considered to be independent Nakagami-$m$. The proposed fusion rule uses the channel statistics, instead of the instantaneous channel state information, and is based on the Neyman-Pearson criteria. Closed-form solutions for the system-level probability of detection and probability of false alarm are also derived. Furthermore, a closed-form expression for the optimal number of cooperative SUs, needed to minimize the total error rate, is presented. The usefulness of factor graph and sum-product-algorithm models for computing likelihoods, is also discussed to highlight its advantage, in terms of computational cost. The performance of the proposed schemes have been evaluated both by analysis and simulations. Results show that the proposed rules perform well over a wide range of the signal-to-noise ratio.
Distributed Multilevel Diversity Coding
Venue: arXiv cs.IT 2015
Year: 2015

In distributed multilevel diversity coding, $K$ correlated sources (each with $K$ components) are encoded in a distributed manner such that, given the outputs from any $α$ encoders, the decoder can reconstruct the first $α$ components of each of the corresponding $α$ sources. For this problem, the optimality of a multilayer Slepian-Wolf coding scheme based on binning and superposition is established when $K\leq 3$. The same conclusion is shown to hold for general $K$ under a certain symmetry condition, which generalizes a celebrated result by Yeung and Zhang.
Cyber physical modeling of distributed resources for distribution system operations
Venue: arXiv cs.CE 2015
Year: 2015

Co-simulation platforms are necessary to study the interactions of complex systems integrated in future smart grids. The Virtual Grid Integration Laboratory (VirGIL) is a modular co-simulation platform designed to study interactions between demand response strategies, building comfort, communication networks, and power system operation. This paper presents the coupling of power systems, buildings, communications and control under a master algorithm. There are two objectives. First, to use a modular architecture for VirGIL, based on the Functional Mock-up Interface (FMI), where several different modules can be added, exchanged, and tested. Second, to use a commercial power system simulation platform, familiar to power system operators, such as DIgSILENT Powerfactory. This will help reduce the barriers to the industry for adopting such platforms, investigate and subsequently deploy demand response strategies in their daily operation. VirGIL further introduces the integration of the Quantized State System (QSS) methods for simulation in this co-simulation platform. Results on how these systems interact using a real network and consumption data are also presented.
Leveraging History for Faster Sampling of Online Social Networks
Venue: arXiv cs.SI 2015
Year: 2015

How to enable efficient analytics over such data has been an increasingly important research problem. Given the sheer size of such social networks, many existing studies resort to sampling techniques that draw random nodes from an online social network through its restrictive web/API interface. Almost all of them use the exact same underlying technique of random walk - a Markov Chain Monte Carlo based method which iteratively transits from one node to its random neighbor. Random walk fits naturally with this problem because, for most online social networks, the only query we can issue through the interface is to retrieve the neighbors of a given node (i.e., no access to the full graph topology). A problem with random walks, however, is the "burn-in" period which requires a large number of transitions/queries before the sampling distribution converges to a stationary value that enables the drawing of samples in a statistically valid manner. In this paper, we consider a novel problem of speeding up the fundamental design of random walks (i.e., reducing the number of queries it requires) without changing the stationary distribution it achieves - thereby enabling a more efficient "drop-in" replacement for existing sampling-based analytics techniques over online social networks. Our main idea is to leverage the history of random walks to construct a higher-ordered Markov chain. We develop two algorithms, Circulated Neighbors and Groupby Neighbors Random Walk (CNRW and GNRW) and prove that, no matter what the social network topology is, CNRW and GNRW offer better efficiency than baseline random walks while achieving the same stationary distribution. We demonstrate through extensive experiments on real-world social networks and synthetic graphs the superiority of our techniques over the existing ones.
Full-Duplex MIMO Relaying Powered by Wireless Energy Transfer
Venue: arXiv cs.IT 2015
Year: 2015

We consider a full-duplex decode-and-forward system, where the wirelessly powered relay employs the time-switching protocol to receive power from the source and then transmit information to the destination. It is assumed that the relay node is equipped with two sets of antennas to enable full-duplex communications. Three different interference mitigation schemes are studied, namely, 1) optimal 2) zero-forcing and 3) maximum ratio combining/maximum ratio transmission. We develop new outage probability expressions to investigate delay-constrained transmission throughput of these schemes. Our analysis show interesting performance comparisons of the considered precoding schemes for different system and link parameters.
On the Effect of Human-Computer Interfaces on Language Expression
Venue: arXiv cs.HC 2015
Year: 2015

Language expression is known to be dependent on attributes intrinsic to the author. To date, however, little attention has been devoted to the effect of interfaces used to articulate language on its expression. Here we study a large corpus of text written using different input devices and show that writers unconsciously prefer different letters depending on the interplay between their individual traits (e.g., hand laterality and injuries) and the layout of keyboards. Our results show, for the first time, how the interplay between technology and its users modifies language expression.
Non-Malleable Extractors and Codes, with their Many Tampered Extensions
Venue: arXiv cs.CR 2015
Year: 2015

Randomness extractors and error correcting codes are fundamental objects in computer science. Recently, there have been several natural generalizations of these objects, in the context and study of tamper resilient cryptography. These are seeded non-malleable extractors, introduced in [DW09]; seedless non-malleable extractors, introduced in [CG14b]; and non-malleable codes, introduced in [DPW10]. However, explicit constructions of non-malleable extractors appear to be hard, and the known constructions are far behind their non-tampered counterparts. In this paper we make progress towards solving the above problems. Our contributions are as follows. (1) We construct an explicit seeded non-malleable extractor for min-entropy $k \geq \log^2 n$. This dramatically improves all previous results and gives a simpler 2-round privacy amplification protocol with optimal entropy loss, matching the best known result in [Li15b]. (2) We construct the first explicit non-malleable two-source extractor for min-entropy $k \geq n-n^{Ω(1)}$, with output size $n^{Ω(1)}$ and error $2^{-n^{Ω(1)}}$. (3) We initiate the study of two natural generalizations of seedless non-malleable extractors and non-malleable codes, where the sources or the codeword may be tampered many times. We construct the first explicit non-malleable two-source extractor with tampering degree $t$ up to $n^{Ω(1)}$, which works for min-entropy $k \geq n-n^{Ω(1)}$, with output size $n^{Ω(1)}$ and error $2^{-n^{Ω(1)}}$. We show that we can efficiently sample uniformly from any pre-image. By the connection in [CG14b], we also obtain the first explicit non-malleable codes with tampering degree $t$ up to $n^{Ω(1)}$, relative rate $n^{Ω(1)}/n$, and error $2^{-n^{Ω(1)}}$.
Quality Control in Crowdsourced Object Segmentation
Venue: arXiv cs.CV 2015
Year: 2015

This paper explores processing techniques to deal with noisy data in crowdsourced object segmentation tasks. We use the data collected with "Click'n'Cut", an online interactive segmentation tool, and we perform several experiments towards improving the segmentation results. First, we introduce different superpixel-based techniques to filter users' traces, and assess their impact on the segmentation result. Second, we present different criteria to detect and discard the traces from potential bad users, resulting in a remarkable increase in performance. Finally, we show a novel superpixel-based segmentation algorithm which does not require any prior filtering and is based on weighting each user's contribution according to his/her level of expertise.