OpenRaiser/Intern-Atlas huggingface dataset:
Understanding VSIDS Branching Heuristics in Conflict-Driven Clause-Learning SAT Solvers
Venue: arXiv cs.LO 2015
Year: 2015

Conflict-Driven Clause-Learning SAT solvers crucially depend on the Variable State Independent Decaying Sum (VSIDS) branching heuristic for their performance. Although VSIDS was proposed nearly fifteen years ago, and many other branching heuristics for SAT solving have since been proposed, VSIDS remains one of the most effective branching heuristics. In this paper, we advance our understanding of VSIDS by answering the following key questions. The first question we pose is "what is special about the class of variables that VSIDS chooses to additively bump?" In answering this question we showed that VSIDS overwhelmingly picks, bumps, and learns bridge variables, defined as the variables that connect distinct communities in the community structure of SAT instances. This is surprising since VSIDS was invented more than a decade before the link between community structure and SAT solver performance was discovered. Additionally, we show that VSIDS viewed as a ranking function correlates strongly with temporal graph centrality measures. Putting these two findings together, we conclude that VSIDS picks high-centrality bridge variables. The second question we pose is "what role does multiplicative decay play in making VSIDS so effective?" We show that the multiplicative decay behaves like an exponential moving average (EMA) that favors variables that persistently occur in conflicts (the signal) over variables that occur intermittently (the noise). The third question we pose is "whether VSIDS is temporally and spatially focused." We show that VSIDS disproportionately picks variables from a few communities unlike, say, the random branching heuristic. We put these findings together to invent a new adaptive VSIDS branching heuristic that solves more instances than one of the best-known VSIDS variants over the SAT Competition 2013 benchmarks.
BayesWipe: A Scalable Probabilistic Framework for Cleaning BigData
Venue: arXiv cs.DB 2015
Year: 2015

Recent efforts in data cleaning of structured data have focused exclusively on problems like data deduplication, record matching, and data standardization; none of the approaches addressing these problems focus on fixing incorrect attribute values in tuples. Correcting values in tuples is typically performed by a minimum cost repair of tuples that violate static constraints like CFDs (which have to be provided by domain experts, or learned from a clean sample of the database). In this paper, we provide a method for correcting individual attribute values in a structured database using a Bayesian generative model and a statistical error model learned from the noisy database directly. We thus avoid the necessity for a domain expert or clean master data. We also show how to efficiently perform consistent query answering using this model over a dirty database, in case write permissions to the database are unavailable. We evaluate our methods over both synthetic and real data.
Socio-Spatial Pareto Frontiers of Twitter Networks
Venue: arXiv cs.SI 2015
Year: 2015

Social media provides a rich source of networked data. This data is represented by a set of nodes and a set of relations (edges). It is often possible to obtain or infer multiple types of relations from the same set of nodes, such as observed friend connections, inferred links via semantic comparison, or relations based off of geographic proximity. These edge sets can be represented by one multi-layer network. In this paper we review a method to perform community detection of multilayer networks, and illustrate its use as a visualization tool for analyzing different community partitions. The algorithm is illustrated on a dataset from Twitter, specifically regarding the National Football League (NFL).
Rate Analysis of Two-Receiver MISO Broadcast Channel with Finite Rate Feedback: A Rate-Splitting Approach
Venue: arXiv cs.IT 2015
Year: 2015

To enhance the multiplexing gain of two-receiver Multiple-Input-Single-Output Broadcast Channel with imperfect channel state information at the transmitter (CSIT), a class of Rate-Splitting (RS) approaches has been proposed recently, which divides one receiver's message into a common and a private part, and superposes the common message on top of Zero-Forcing precoded private messages. In this paper, with quantized CSIT, we study the ergodic sum rate of two schemes, namely RS-S and RS-ST, where the common message(s) are transmitted via a space and space-time design, respectively. Firstly, we upper-bound the sum rate loss incurred by each scheme relative to Zero-Forcing Beamforming (ZFBF) with perfect CSIT. Secondly, we show that, to maintain a constant sum rate loss, RS-S scheme enables a feedback overhead reduction over ZFBF with quantized CSIT. Such reduction scales logarithmically with the constant rate loss at high Signal-to-Noise-Ratio (SNR). We also find that, compared to RS-S scheme, RS-ST scheme offers a further feedback overhead reduction that scales with the discrepancy between the feedback overhead employed by the two receivers when there are alternating receiver-specific feedback qualities. Finally, simulation results show that both schemes offer a significant SNR gain over conventional single-user/multiuser mode switching when the feedback overhead is fixed.
Improved Spanning Ratio for Low Degree Plane Spanners
Venue: arXiv cs.CG 2015
Year: 2015

We describe an algorithm that builds a plane spanner with a maximum degree of 8 and a spanning ratio of approximately 4.414 with respect to the complete graph. This is the best currently known spanning ratio for a plane spanner with a maximum degree of less than 14.
The Potential of the Intel Xeon Phi for Supervised Deep Learning
Venue: arXiv cs.DC 2015
Year: 2015

Supervised learning of Convolutional Neural Networks (CNNs), also known as supervised Deep Learning, is a computationally demanding process. To find the most suitable parameters of a network for a given application, numerous training sessions are required. Therefore, reducing the training time per session is essential to fully utilize CNNs in practice. While numerous research groups have addressed the training of CNNs using GPUs, so far not much attention has been paid to the Intel Xeon Phi coprocessor. In this paper we investigate empirically and theoretically the potential of the Intel Xeon Phi for supervised learning of CNNs. We design and implement a parallelization scheme named CHAOS that exploits both the thread- and SIMD-parallelism of the coprocessor. Our approach is evaluated on the Intel Xeon Phi 7120P using the MNIST dataset of handwritten digits for various thread counts and CNN architectures. Results show a 103.5x speed up when training our large network for 15 epochs using 244 threads, compared to one thread on the coprocessor. Moreover, we develop a performance model and use it to assess our implementation and answer what-if questions.
Comment partitionner automatiquement des marches aléatoires ? Avec application à la finance quantitative
Venue: arXiv cs.CE 2015
Year: 2015

We present in this paper a novel non-parametric approach useful for clustering Markov processes. We introduce a pre-processing step consisting in mapping multivariate independent and identically distributed samples from random variables to a generic non-parametric representation which factorizes dependency and marginal distribution apart without losing any. An associated metric is defined where the balance between random variables dependency and distribution information is controlled by a single parameter. This mixing parameter can be learned or played with by a practitioner, such use is illustrated on the case of clustering financial time series. Experiments, implementation and results obtained on public financial time series are online on a web portal \url{http://www.datagrapple.com}.
On anthropomorphic decision making in a model observer
Venue: arXiv cs.CV 2015
Year: 2015

By analyzing human readers' performance in detecting small round lesions in simulated digital breast tomosynthesis background in a location known exactly scenario, we have developed a model observer that is a better predictor of human performance with different levels of background complexity (i.e., anatomical and quantum noise). Our analysis indicates that human observers perform a lesion detection task by combining a number of sub-decisions, each an indicator of the presence of a lesion in the image stack. This is in contrast to a channelized Hotelling observer, where the detection task is conducted holistically by thresholding a single decision variable, made from an optimally weighted linear combination of channels. However, it seems that the sub-par performance of human readers compared to the CHO cannot be fully explained by their reliance on sub-decisions, or perhaps we do not consider a sufficient number of sub-decisions. To bridge the gap between the performances of human readers and the model observer based upon sub-decisions, we use an additive noise model, the power of which is modulated with the level of background complexity. The proposed model observer better predicts the fast drop in human detection performance with background complexity.
Discovering Characteristic Landmarks on Ancient Coins using Convolutional Networks
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we propose a novel method to find characteristic landmarks on ancient Roman imperial coins using deep convolutional neural network models (CNNs). We formulate an optimization problem to discover class-specific regions while guaranteeing specific controlled loss of accuracy. Analysis on visualization of the discovered region confirms that not only can the proposed method successfully find a set of characteristic regions per class, but also the discovered region is consistent with human expert annotations. We also propose a new framework to recognize the Roman coins which exploits hierarchical structure of the ancient Roman coins using the state-of-the-art classification power of the CNNs adopted to a new task of coin classification. Experimental results show that the proposed framework is able to effectively recognize the ancient Roman coins. For this research, we have collected a new Roman coin dataset where all coins are annotated and consist of observe (head) and reverse (tail) images.
Private Approximations of the 2nd-Moment Matrix Using Existing Techniques in Linear Regression
Venue: arXiv cs.DS 2015
Year: 2015

We introduce three differentially-private algorithms that approximates the 2nd-moment matrix of the data. These algorithm, which in contrast to existing algorithms output positive-definite matrices, correspond to existing techniques in linear regression literature. Specifically, we discuss the following three techniques. (i) For Ridge Regression, we propose setting the regularization coefficient so that by approximating the solution using Johnson-Lindenstrauss transform we preserve privacy. (ii) We show that adding a small batch of random samples to our data preserves differential privacy. (iii) We show that sampling the 2nd-moment matrix from a Bayesian posterior inverse-Wishart distribution is differentially private provided the prior is set correctly. We also evaluate our techniques experimentally and compare them to the existing "Analyze Gauss" algorithm of Dwork et al.
Capacity of Coded Index Modulation
Venue: arXiv cs.IT 2015
Year: 2015

We consider the special case of index coding over the Gaussian broadcast channel where each receiver has prior knowledge of a subset of messages at the transmitter and demands all the messages from the source. We propose a concatenated coding scheme for this problem, using an index code for the Gaussian channel as an inner code/modulation to exploit side information at the receivers, and an outer code to attain coding gain against the channel noise. We derive the capacity region of this scheme by viewing the resulting channel as a multiple-access channel with many receivers, and relate it to the 'side information gain' -- which is a measure of the advantage of a code in utilizing receiver side information -- of the inner index code/modulation. We demonstrate the utility of the proposed architecture by simulating the performance of an index code/modulation concatenated with an off-the-shelf convolutional code through bit-interleaved coded-modulation.
Randomized Revenue Monotone Mechanisms for Online Advertising
Venue: arXiv cs.GT 2015
Year: 2015

Online advertising is the main source of revenue for many Internet firms. A central component of online advertising is the underlying mechanism that selects and prices the winning ads for a given ad slot. In this paper we study designing a mechanism for the Combinatorial Auction with Identical Items (CAII) in which we are interested in selling $k$ identical items to a group of bidders each demanding a certain number of items between $1$ and $k$. CAII generalizes important online advertising scenarios such as image-text and video-pod auctions [GK14]. In image-text auction we want to fill an advertising slot on a publisher's web page with either $k$ text-ads or a single image-ad and in video-pod auction we want to fill an advertising break of $k$ seconds with video-ads of possibly different durations. Our goal is to design truthful mechanisms that satisfy Revenue Monotonicity (RM). RM is a natural constraint which states that the revenue of a mechanism should not decrease if the number of participants increases or if a participant increases her bid. [GK14] showed that no deterministic RM mechanism can attain PoRM of less than $\ln(k)$ for CAII, i.e., no deterministic mechanism can attain more than $\frac{1}{\ln(k)}$ fraction of the maximum social welfare. [GK14] also design a mechanism with PoRM of $O(\ln^2(k))$ for CAII. In this paper, we seek to overcome the impossibility result of [GK14] for deterministic mechanisms by using the power of randomization. We show that by using randomization, one can attain a constant PoRM. In particular, we design a randomized RM mechanism with PoRM of $3$ for CAII.
Aspect OntoMaven - Aspect-Oriented Ontology Development and Configuration With OntoMaven
Venue: arXiv cs.SE 2015
Year: 2015

In agile ontology-based software engineering projects support for modular reuse of ontologies from large existing remote repositories, ontology project life cycle management, and transitive dependency management are important needs. The contribution of this paper is a new design artifact called OntoMaven combined with a unified approach to ontology modularization, aspect-oriented ontology development, which was inspired by aspect-oriented programming. OntoMaven adopts the Apache Maven-based development methodology and adapts its concepts to knowledge engineering for Maven-based ontology development and management of ontology artifacts in distributed ontology repositories. The combination with aspect-oriented ontology development allows for fine-grained, declarative configuration of ontology modules.
Performance analysis of a Tor-like onion routing implementation
Venue: arXiv cs.DC 2015
Year: 2015

The current onion routing implementation of Tribler works as expected but throttles the overall throughput of the Tribler system. This article discusses a measuring procedure to reproducibly profile the tunnel implementation so further optimizations of the tunnel community can be made. Our work has been integrated into the Tribler eco-system.
Rencontre improbable entre von Foerster et Snowden
Venue: arXiv cs.CY 2015
Year: 2015

Although ICT have created hope for a shared pluralistic world, democratic principles are far from being respected in the public digital environment, and require a detailed knowledge of the laws by which they are governed. Von Foerster's conjecture is one of the early theoretical results that could help to understand these laws. Although neglected since a long time, the advent of the overlying layer of recommendation and ranking mechanisms which is progressively occupying the Web has given empirical evidences of this conjecture, which predicts the consequences of increasing inter-individual influences on social dynamics and the susceptibility of these latter to manipulation. With both von Foerster's conjecture and the Snowden revelations in the background, we analyse the impact of ICT on human societies and their governance, in view of the fact that they have a massive impact on the way in which people influence each other in their tastes and actions.
An Empirical Evaluation of True Online TD(λ)
Venue: arXiv cs.AI 2015
Year: 2015

The true online TD(λ) algorithm has recently been proposed (van Seijen and Sutton, 2014) as a universal replacement for the popular TD(λ) algorithm, in temporal-difference learning and reinforcement learning. True online TD(λ) has better theoretical properties than conventional TD(λ), and the expectation is that it also results in faster learning. In this paper, we put this hypothesis to the test. Specifically, we compare the performance of true online TD(λ) with that of TD(λ) on challenging examples, random Markov reward processes, and a real-world myoelectric prosthetic arm. We use linear function approximation with tabular, binary, and non-binary features. We assess the algorithms along three dimensions: computational cost, learning speed, and ease of use. Our results confirm the strength of true online TD(λ): 1) for sparse feature vectors, the computational overhead with respect to TD(λ) is minimal; for non-sparse features the computation time is at most twice that of TD(λ), 2) across all domains/representations the learning speed of true online TD(λ) is often better, but never worse than that of TD(λ), and 3) true online TD(λ) is easier to use, because it does not require choosing between trace types, and it is generally more stable with respect to the step-size. Overall, our results suggest that true online TD(λ) should be the first choice when looking for an efficient, general-purpose TD method.
Cooperative H-infinity Estimation for Large-Scale Interconnected Linear Systems
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, a synthesis method for distributed estimation is presented, which is suitable for dealing with large-scale interconnected linear systems with disturbance. The main feature of the proposed method is that local estimators only estimate a reduced set of state variables and their complexity does not increase with the size of the system. Nevertheless, the local estimators are able to deal with lack of local detectability. Moreover, the estimators guarantee H-infinity-performance of the estimates with respect to model and measurement disturbances.
Characterization and recognition of some opposition and coalition graph classes
Venue: arXiv cs.DM 2015
Year: 2015

A graph is an opposition graph, respectively, a coalition graph, if it admits an acyclic orientation which puts the two end-edges of every chordless 4-vertex path in opposition, respectively, in the same direction. Opposition and coalition graphs have been introduced and investigated in connection to perfect graphs. Recognizing and characterizing opposition and coalition graphs are long-standing open problems. This paper gives characterizations for opposition graphs and coalition graphs on some restricted graph classes. Implicit in our arguments are polynomial time recognition algorithms for these graphs. We also give a good characterization for the so-called generalized opposition graphs.
Flip the Cloud: Cyber-Physical Signaling Games in the Presence of Advanced Persistent Threats
Venue: arXiv cs.CR 2015
Year: 2015

Access to the cloud has the potential to provide scalable and cost effective enhancements of physical devices through the use of advanced computational processes run on apparently limitless cyber infrastructure. On the other hand, cyber-physical systems and cloud-controlled devices are subject to numerous design challenges; among them is that of security. In particular, recent advances in adversary technology pose Advanced Persistent Threats (APTs) which may stealthily and completely compromise a cyber system. In this paper, we design a framework for the security of cloud-based systems that specifies when a device should trust commands from the cloud which may be compromised. This interaction can be considered as a game between three players: a cloud defender/administrator, an attacker, and a device. We use traditional signaling games to model the interaction between the cloud and the device, and we use the recently proposed FlipIt game to model the struggle between the defender and attacker for control of the cloud. Because attacks upon the cloud can occur without knowledge of the defender, we assume that strategies in both games are picked according to prior commitment. This framework requires a new equilibrium concept, which we call Gestalt Equilibrium, a fixed-point that expresses the interdependence of the signaling and FlipIt games. We present the solution to this fixed-point problem under certain parameter cases, and illustrate an example application of cloud control of an unmanned vehicle. Our results contribute to the growing understanding of cloud-controlled systems.
Fixed parameter complexity of distance constrained labeling and uniform channel assignment problems
Venue: arXiv cs.DM 2015
Year: 2015

We study computational complexity of the class of distance-constrained graph labeling problems from the fixed parameter tractability point of view. The parameters studied are neighborhood diversity and clique width. We rephrase the distance constrained graph labeling problem as a specific uniform variant of the Channel Assignment problem and show that this problem is fixed parameter tractable when parameterized by the neighborhood diversity together with the largest weight. Consequently, every $L(p_1, p_2, \dots, p_k)$-labeling problem is FPT when parameterized by the neighborhood diversity, the maximum $p_i$ and $k.$ Our results yield also FPT algorithms for all $L(p_1, p_2, \dots, p_k)$-labeling problems when parameterized by the size of a minimum vertex cover, answering an open question of Fiala et al.: Parameterized complexity of coloring problems: Treewidth versus vertex cover. The same consequence applies on Channel Assignment when the maximum weight is additionally included among the parameters. Finally, we show that the uniform variant of the Channel Assignment problem becomes NP-complete when generalized to graphs of bounded clique width.
SQL for SRL: Structure Learning Inside a Database System
Venue: arXiv cs.LG 2015
Year: 2015

The position we advocate in this paper is that relational algebra can provide a unified language for both representing and computing with statistical-relational objects, much as linear algebra does for traditional single-table machine learning. Relational algebra is implemented in the Structured Query Language (SQL), which is the basis of relational database management systems. To support our position, we have developed the FACTORBASE system, which uses SQL as a high-level scripting language for statistical-relational learning of a graphical model structure. The design philosophy of FACTORBASE is to manage statistical models as first-class citizens inside a database. Our implementation shows how our SQL constructs in FACTORBASE facilitate fast, modular, and reliable program development. Empirical evidence from six benchmark databases indicates that leveraging database system capabilities achieves scalable model structure learning.
Centralized and Distributed Newton Methods for Network Optimization and Extensions
Venue: arXiv cs.NA 2015
Year: 2015

We consider Newton methods for common types of single commodity and multi-commodity network flow problems. Despite the potentially very large dimension of the problem, they can be implemented using the conjugate gradient method and low-dimensional network operations, as shown nearly thirty years ago. We revisit these methods, compare them to more recent proposals, and describe how they can be implemented in a distributed computing system. We also discuss generalizations, including the treatment of arc gains, linear side constraints, and related special structures.