OpenRaiser/Intern-Atlas huggingface dataset:
Combining Probabilistic, Causal, and Normative Reasoning in CP-logic
Venue: arXiv cs.AI 2015
Year: 2015

In recent years the search for a proper formal definition of actual causation -- i.e., the relation of cause-effect as it is instantiated in specific observations, rather than general causal relations -- has taken on impressive proportions. In part this is due to the insight that this concept plays a fundamental role in many different fields, such as legal theory, engineering, medicine, ethics, etc. Because of this diversity in applications, some researchers have shifted focus from a single idealized definition towards a more pragmatic, context-based account. For instance, recent work by Halpern and Hitchcock draws on empirical research regarding people's causal judgments, to suggest a graded and context-sensitive notion of causation. Although we sympathize with many of their observations, their restriction to a merely qualitative ordering runs into trouble for more complex examples. Therefore we aim to improve on their approach, by using the formal language of CP-logic (Causal Probabilistic logic), and the framework for defining actual causation that was developed by the current authors using it. First we rephrase their ideas into our quantitative, probabilistic setting, after which we modify it to accommodate a greater class of examples. Further, we introduce a formal distinction between statistical and normative considerations.
Distributed Hierarchical Control versus an Economic Model for Cloud Resource Management
Venue: arXiv cs.DC 2015
Year: 2015

We investigate a hierarchically organized cloud infrastructure and compare distributed hierarchical control based on resource monitoring with market mechanisms for resource management. The latter do not require a model of the system, incur a low overhead, are robust, and satisfy several other desiderates of autonomic computing. We introduce several performance measures and report on simulation studies which show that a straightforward bidding scheme supports an effective admission control mechanism, while reducing the communication complexity by several orders of magnitude and also increasing the acceptance rate compared to hierarchical control and monitoring mechanisms. Resource management based on market-based mechanisms can be seen as an intermediate step towards cloud self-organization, an ideal alternative to current mechanisms for cloud resource management.
ROSA: Robust sparse adaptive channel estimation in the presence of impulsive noises
Venue: arXiv cs.IT 2015
Year: 2015

Based on the assumption of Gaussian noise model, conventional adaptive filtering algorithms for reconstruction sparse channels were proposed to take advantage of channel sparsity due to the fact that broadband wireless channels usually have the sparse nature. However, state-of-the-art algorithms are vulnerable to deteriorate under the assumption of non-Gaussian noise models (e.g., impulsive noise) which often exist in many advanced communications systems. In this paper, we study the problem of RObust Sparse Adaptive channel estimation (ROSA) in the environment of impulsive noises using variable step-size affine projection sign algorithm (VSS-APSA). Specifically, standard VSS-APSA algorithm is briefly reviewed and three sparse VSS-APSA algorithms are proposed to take advantage of channel sparsity with different sparse constraints. To fairly evaluate the performance of these proposed algorithms, alpha-stable noise is considered to approximately model the realistic impulsive noise environments. Simulation results show that the proposed algorithms can achieve better performance than standard VSS-APSA algorithm in different impulsive environments.
Complexity and universality in the long-range order of words
Venue: arXiv cs.CL 2015
Year: 2015

As is the case of many signals produced by complex systems, language presents a statistical structure that is balanced between order and disorder. Here we review and extend recent results from quantitative characterisations of the degree of order in linguistic sequences that give insights into two relevant aspects of language: the presence of statistical universals in word ordering, and the link between semantic information and the statistical linguistic structure. We first analyse a measure of relative entropy that assesses how much the ordering of words contributes to the overall statistical structure of language. This measure presents an almost constant value close to 3.5 bits/word across several linguistic families. Then, we show that a direct application of information theory leads to an entropy measure that can quantify and extract semantic structures from linguistic samples, even without prior knowledge of the underlying language.
S-Store: Streaming Meets Transaction Processing
Venue: arXiv cs.DB 2015
Year: 2015

Stream processing addresses the needs of real-time applications. Transaction processing addresses the coordination and safety of short atomic computations. Heretofore, these two modes of operation existed in separate, stove-piped systems. In this work, we attempt to fuse the two computational paradigms in a single system called S-Store. In this way, S-Store can simultaneously accommodate OLTP and streaming applications. We present a simple transaction model for streams that integrates seamlessly with a traditional OLTP system. We chose to build S-Store as an extension of H-Store, an open-source, in-memory, distributed OLTP database system. By implementing S-Store in this way, we can make use of the transaction processing facilities that H-Store already supports, and we can concentrate on the additional implementation features that are needed to support streaming. Similar implementations could be done using other main-memory OLTP platforms. We show that we can actually achieve higher throughput for streaming workloads in S-Store than an equivalent deployment in H-Store alone. We also show how this can be achieved within H-Store with the addition of a modest amount of new functionality. Furthermore, we compare S-Store to two state-of-the-art streaming systems, Spark Streaming and Storm, and show how S-Store matches and sometimes exceeds their performance while providing stronger transactional guarantees.
Counting Inversions Adaptively
Venue: arXiv cs.DS 2015
Year: 2015

We give a simple and efficient algorithm for adaptively counting inversions in a sequence of $n$ integers. Our algorithm runs in $O(n + n \sqrt{\lg{(Inv/n)}})$ time in the word-RAM model of computation, where $Inv$ is the number of inversions.
Low-dimensional Models in Spatio-Temporal Wind Speed Forecasting
Venue: arXiv cs.SY 2015
Year: 2015

Integrating wind power into the grid is challenging because of its random nature. Integration is facilitated with accurate short-term forecasts of wind power. The paper presents a spatio-temporal wind speed forecasting algorithm that incorporates the time series data of a target station and data of surrounding stations. Inspired by Compressive Sensing (CS) and structured-sparse recovery algorithms, we claim that there usually exists an intrinsic low-dimensional structure governing a large collection of stations that should be exploited. We cast the forecasting problem as recovery of a block-sparse signal $\boldsymbol{x}$ from a set of linear equations $\boldsymbol{b} = A\boldsymbol{x}$ for which we propose novel structure-sparse recovery algorithms. Results of a case study in the east coast show that the proposed Compressive Spatio-Temporal Wind Speed Forecasting (CST-WSF) algorithm significantly improves the short-term forecasts compared to a set of widely-used benchmark models.
The concept "altruism" for sociological research: from conceptualization to operationalization
Venue: arXiv cs.CY 2015
Year: 2015

This article addresses the question of the relevant conceptualization of «altruism» in Russian from the perspective sociological research operationalization. It investigates the spheres of social application of the word «altruism», include Russian equivalent «vzaimopomoshh`» (mutual help). The data for the study comes from Russian National Corpus (Russian). The theoretical framework consists of Paul F. Lazarsfeld`s Theory of Sociological Research Methodology and the Natural Semantic Metalanguage (NSM). Quantitative analysis shows features in the representation of altruism in Russian that sociologists need to know in the preparation of questionnaires, interview guides and analysis of transcripts.
Accelerating Consensus by Spectral Clustering and Polynomial Filters
Venue: arXiv cs.SY 2015
Year: 2015

It is known that polynomial filtering can accelerate the convergence towards average consensus on an undirected network. In this paper the gain of a second-order filtering is investigated. A set of graphs is determined for which consensus can be attained in finite time, and a preconditioner is proposed to adapt the undirected weights of any given graph to achieve fastest convergence with the polynomial filter. The corresponding cost function differs from the traditional spectral gap, as it favors grouping the eigenvalues in two clusters. A possible loss of robustness of the polynomial filter is also highlighted.
Research Data Explored II: the Anatomy and Reception of figshare
Venue: arXiv cs.DL 2015
Year: 2015

This is the second paper in a series of bibliometric studies of research data. In this paper, we present an analysis of figshare, one of the largest multidisciplinary repositories for research materials to date. We analysed the structure of items archived in figshare, their usage, and their reception in two altmetrics sources (PlumX and ImpactStory). We found that figshare acts (1) as a personal repository for yet unpublished materials, (2) as a platform for newly published research materials, and (3) as an archive for PLOS. Depending on the function, we found different bibliometric characteristics. Items archived from PLOS tend to be coming from the natural sciences and are often unviewed and non-downloaded. Self-archived items, however, come from a variety of disciplines and exhibit some patterns of higher usage. In the altmetrics analysis, we found that Twitter was the social media service where research data gained most attention; generally, research data published in 2014 were most popular across social media services. PlumX detects considerably more items in social media and also finds higher altmetric scores than ImpactStory.
An Incentivized Approach for Fair Participation in Wireless Ad hoc Networks
Venue: arXiv cs.NI 2015
Year: 2015

In Wireless Ad hoc networks (WANETs), nodes separated by considerable distance communicate with each other by relaying their messages through other nodes. However, it might not be in the best interests of a node to forward the message of another node due to power constraints. In addition, all nodes being rational, some nodes may be selfish, i.e. they might not relay data from other nodes so as to increase their lifetime. In this paper, we present a fair and incentivized approach for participation in Ad hoc networks. Given the power required for each transmission, we are able to determine the power saving contributed by each intermediate hop. We propose the FAir Share incenTivizEd Ad hoc paRticipation protocol (FASTER), which takes a selected route from a routing protocol as input, to calculate the worth of each node using the cooperative game theory concept of 'Shapley Value' applied on the power saved by each node. This value can be used for allocation of Virtual Currency to the nodes, which can be spent on subsequent message transmissions.
The business model bank: conceptualizing a database structure for large-sample study of an emerging management concept
Venue: arXiv cs.CY 2015
Year: 2015

The business model represents an increasingly important management concept. However, progress in research related to the concept is currently inhibited from inconsistencies in terms of formalizing and therewith also empirically measuring the business model concept. Taking this as a starting point, this paper offers a conceptualization for building a scalable database to rigorously capture large samples of business models. The following contributions are made: First, we suggest a concept for dimensions to be modeled in the database. Second, we discuss issues critical to the scalability of such an endeavor. Third, we point to empirical and simulation-based studies enabled by the population of such a database. Considerations for theory and practice are offered.
Partial Sum Minimization of Singular Values in Robust PCA: Algorithm and Applications
Venue: arXiv cs.CV 2015
Year: 2015

Robust Principal Component Analysis (RPCA) via rank minimization is a powerful tool for recovering underlying low-rank structure of clean data corrupted with sparse noise/outliers. In many low-level vision problems, not only it is known that the underlying structure of clean data is low-rank, but the exact rank of clean data is also known. Yet, when applying conventional rank minimization for those problems, the objective function is formulated in a way that does not fully utilize a priori target rank information about the problems. This observation motivates us to investigate whether there is a better alternative solution when using rank minimization. In this paper, instead of minimizing the nuclear norm, we propose to minimize the partial sum of singular values, which implicitly encourages the target rank constraint. Our experimental analyses show that, when the number of samples is deficient, our approach leads to a higher success rate than conventional rank minimization, while the solutions obtained by the two approaches are almost identical when the number of samples is more than sufficient. We apply our approach to various low-level vision problems, e.g. high dynamic range imaging, motion edge detection, photometric stereo, image alignment and recovery, and show that our results outperform those obtained by the conventional nuclear norm rank minimization method.
Do We Need More Training Data?
Venue: arXiv cs.CV 2015
Year: 2015

Datasets for training object recognition systems are steadily increasing in size. This paper investigates the question of whether existing detectors will continue to improve as data grows, or saturate in performance due to limited model complexity and the Bayes risk associated with the feature spaces in which they operate. We focus on the popular paradigm of discriminatively trained templates defined on oriented gradient features. We investigate the performance of mixtures of templates as the number of mixture components and the amount of training data grows. Surprisingly, even with proper treatment of regularization and "outliers", the performance of classic mixture models appears to saturate quickly ($\sim$10 templates and $\sim$100 positive training examples per template). This is not a limitation of the feature space as compositional mixtures that share template parameters via parts and that can synthesize new templates not encountered during training yield significantly better performance. Based on our analysis, we conjecture that the greatest gains in detection performance will continue to derive from improved representations and learning algorithms that can make efficient use of large datasets.
Coordinated Two-Tier Heterogeneous Cellular Networks with Leakage Based Beamforming
Venue: arXiv cs.IT 2015
Year: 2015

In this paper we demonstrate the rate gains achieved by two-tier heterogeneous cellular networks (HetNets) with varying degrees of coordination between macrocell and microcell base stations (BSs). We show that without the presence of coordination, network densification does not provide any gain in the sum rate and rapidly decreases the mean per-user signal-to-interference-plus-noise-ratio (SINR). Our results show that coordination reduces the rate of SINR decay with increasing numbers of microcell BSs in the system. Validity of the analytically approximated mean per-user SINR over a wide range of signal-to-noise-ratio (SNR) is demonstrated via comparison with the simulated results.
Adaptively Secure Coin-Flipping, Revisited
Venue: arXiv cs.CR 2015
Year: 2015

The full-information model was introduced by Ben-Or and Linial in 1985 to study collective coin-flipping: the problem of generating a common bounded-bias bit in a network of $n$ players with $t=t(n)$ faults. They showed that the majority protocol can tolerate $t=O(\sqrt n)$ adaptive corruptions, and conjectured that this is optimal in the adaptive setting. Lichtenstein, Linial, and Saks proved that the conjecture holds for protocols in which each player sends a single bit. Their result has been the main progress on the conjecture in the last 30 years. In this work we revisit this question and ask: what about protocols involving longer messages? Can increased communication allow for a larger fraction of faulty players? We introduce a model of strong adaptive corruptions, where in each round, the adversary sees all messages sent by honest parties and, based on the message content, decides whether to corrupt a party (and intercept his message) or not. We prove that any one-round coin-flipping protocol, regardless of message length, is secure against at most $\tilde{O}(\sqrt n)$ strong adaptive corruptions. Thus, increased message length does not help in this setting. We then shed light on the connection between adaptive and strongly adaptive adversaries, by proving that for any symmetric one-round coin-flipping protocol secure against $t$ adaptive corruptions, there is a symmetric one-round coin-flipping protocol secure against $t$ strongly adaptive corruptions. Returning to the standard adaptive model, we can now prove that any symmetric one-round protocol with arbitrarily long messages can tolerate at most $\tilde{O}(\sqrt n)$ adaptive corruptions. At the heart of our results lies a novel use of the Minimax Theorem and a new technique for converting any one-round secure protocol into a protocol with messages of $polylog(n)$ bits. This technique may be of independent interest.
Gaussian Mixture Model Based Contrast Enhancement
Venue: arXiv cs.MM 2015
Year: 2015

In this paper, a method for enhancing low contrast images is proposed. This method, called Gaussian Mixture Model based Contrast Enhancement (GMMCE), brings into play the Gaussian mixture modeling of histograms to model the content of the images. Based on the fact that each homogeneous area in natural images has a Gaussian-shaped histogram, it decomposes the narrow histogram of low contrast images into a set of scaled and shifted Gaussians. The individual histograms are then stretched by increasing their variance parameters, and are diffused on the entire histogram by scattering their mean parameters, to build a broad version of the histogram. The number of Gaussians as well as their parameters are optimized to set up a GMM with lowest approximation error and highest similarity to the original histogram. Compared to the existing histogram-based methods, the experimental results show that the quality of GMMCE enhanced pictures are mostly consistent and outperform other benchmark methods. Additionally, the computational complexity analysis show that GMMCE is a low complexity method.
GDC 2: Compression of large collections of genomes
Venue: arXiv cs.DS 2015
Year: 2015

The fall of prices of the high-throughput genome sequencing changes the landscape of modern genomics. A number of large scale projects aimed at sequencing many human genomes are in progress. Genome sequencing also becomes an important aid in the personalized medicine. One of the significant side effects of this change is a necessity of storage and transfer of huge amounts of genomic data. In this paper we deal with the problem of compression of large collections of complete genomic sequences. We propose an algorithm that is able to compress the collection of 1092 human diploid genomes about 9,500 times. This result is about 4 times better than what is offered by the other existing compressors. Moreover, our algorithm is very fast as it processes the data with speed 200MB/s on a modern workstation. In a consequence the proposed algorithm allows storing the complete genomic collections at low cost, e.g., the examined collection of 1092 human genomes needs only about 700MB when compressed, what can be compared to about 6.7 TB of uncompressed FASTA files. The source code is available at http://sun.aei.polsl.pl/REFRESH/index.php?page=projects&project=gdc&subpage=about.
Conferences vs. Journals: Throwing the baby out with the bath water?
Venue: arXiv cs.DL 2015
Year: 2015

Criticism of the conference model should be put in context. Evidences suggest that the essential features of this model have emerged as responses to challenges posed by current trends of scientific research and the impact of the new techno-economic paradigm, the age of Information and Communication Technology. This context seems indispensable when discussing today's problems of scientific evaluation, in particular the Conference vs. Journal (CvJ) debate. This debate, also, would benefit from systematic historical and sociological studies of these practices. In this note we briefly develop these arguments.
Sequential Posted Price Mechanisms with Correlated Valuations
Venue: arXiv cs.GT 2015
Year: 2015

We study the revenue performance of sequential posted price mechanisms and some natural extensions, for a general setting where the valuations of the buyers are drawn from a correlated distribution. Sequential posted price mechanisms are conceptually simple mechanisms that work by proposing a take-it-or-leave-it offer to each buyer. We apply sequential posted price mechanisms to single-parameter multi-unit settings in which each buyer demands only one item and the mechanism can assign the service to at most k of the buyers. For standard sequential posted price mechanisms, we prove that with the valuation distribution having finite support, no sequential posted price mechanism can extract a constant fraction of the optimal expected revenue, even with unlimited supply. We extend this result to the the case of a continuous valuation distribution when various standard assumptions hold simultaneously. In fact, it turns out that the best fraction of the optimal revenue that is extractable by a sequential posted price mechanism is proportional to ratio of the highest and lowest possible valuation. We prove that for two simple generalizations of these mechanisms, a better revenue performance can be achieved: if the sequential posted price mechanism has for each buyer the option of either proposing an offer or asking the buyer for its valuation, then a Omega(1/max{1,d}) fraction of the optimal revenue can be extracted, where d denotes the degree of dependence of the valuations, ranging from complete independence (d=0) to arbitrary dependence (d=n-1). Moreover, when we generalize the sequential posted price mechanisms further, such that the mechanism has the ability to make a take-it-or-leave-it offer to the i-th buyer that depends on the valuations of all buyers except i's, we prove that a constant fraction (2-sqrt{e})/4~0.088 of the optimal revenue can be always be extracted.
Quotient Complexities of Atoms in Regular Ideal Languages
Venue: arXiv cs.FL 2015
Year: 2015

A (left) quotient of a language $L$ by a word $w$ is the language $w^{-1}L=\{x\mid wx\in L\}$. The quotient complexity of a regular language $L$ is the number of quotients of $L$; it is equal to the state complexity of $L$, which is the number of states in a minimal deterministic finite automaton accepting $L$. An atom of $L$ is an equivalence class of the relation in which two words are equivalent if for each quotient, they either are both in the quotient or both not in it; hence it is a non-empty intersection of complemented and uncomplemented quotients of $L$. A right (respectively, left and two-sided) ideal is a language $L$ over an alphabet $Σ$ that satisfies $L=LΣ^*$ (respectively, $L=Σ^*L$ and $L=Σ^*LΣ^*$). We compute the maximal number of atoms and the maximal quotient complexities of atoms of right, left and two-sided regular ideals.