OpenRaiser/Intern-Atlas huggingface dataset:
Fast Non-Parametric Tests of Relative Dependency and Similarity
Venue: arXiv cs.AI 2016
Year: 2016

We introduce two novel non-parametric statistical hypothesis tests. The first test, called the relative test of dependency, enables us to determine whether one source variable is significantly more dependent on a first target variable or a second. Dependence is measured via the Hilbert-Schmidt Independence Criterion (HSIC). The second test, called the relative test of similarity, is use to determine which of the two samples from arbitrary distributions is significantly closer to a reference sample of interest and the relative measure of similarity is based on the Maximum Mean Discrepancy (MMD). To construct these tests, we have used as our test statistics the difference of HSIC statistics and of MMD statistics, respectively. The resulting tests are consistent and unbiased, and have favorable convergence properties. The effectiveness of the relative dependency test is demonstrated on several real-world problems: we identify languages groups from a multilingual parallel corpus, and we show that tumor location is more dependent on gene expression than chromosome imbalance. We also demonstrate the performance of the relative test of similarity over a broad selection of model comparisons problems in deep generative models.
Maximizing a Submodular Function with Viability Constraints
Venue: arXiv cs.DS 2016
Year: 2016

We study the problem of maximizing a monotone submodular function with viability constraints. This problem originates from computational biology, where we are given a phylogenetic tree over a set of species and a directed graph, the so-called food web, encoding viability constraints between these species. These food webs usually have constant {depth}. The goal is to select a subset of $k$ species that satisfies the viability constraints and has maximal phylogenetic diversity. As this problem is known to be NP-hard, we investigate approximation algorithms. We present the first constant factor approximation algorithm if the depth is constant. Its approximation ratio is $(1-\frac{1}{\sqrt{e}})$. This algorithm not only applies to phylogenetic trees with viability constraints but for arbitrary monotone submodular set functions with viability constraints. Second, we show that there is no $(1-1/e+ε)$-approximation algorithm for our problem setting (even for additive functions) and that there is no approximation algorithm for a slight extension of this setting.
How Lock-free Data Structures Perform in Dynamic Environments: Models and Analyses
Venue: arXiv cs.DC 2016
Year: 2016

In this paper we present two analytical frameworks for calculating the performance of lock-free data structures. Lock-free data structures are based on retry loops and are called by application-specific routines. In contrast to previous work, we consider in this paper lock-free data structures in dynamic environments. The size of each of the retry loops, and the size of the application routines invoked in between, are not constant but may change dynamically. The new frameworks follow two different approaches. The first framework, the simplest one, is based on queuing theory. It introduces an average-based approach that facilitates a more coarse-grained analysis, with the benefit of being ignorant of size distributions. Because of this independence from the distribution nature it covers a set of complicated designs. The second approach, instantiated with an exponential distribution for the size of the application routines, uses Markov chains, and is tighter because it constructs stochastically the execution, step by step. Both frameworks provide a performance estimate which is close to what we observe in practice. We have validated our analysis on (i) several fundamental lock-free data structures such as stacks, queues, deques and counters, some of them employing helping mechanisms, and (ii) synthetic tests covering a wide range of possible lock-free designs. We show the applicability of our results by introducing new back-off mechanisms, tested in application contexts, and by designing an efficient memory management scheme that typical lock-free algorithms can utilize.
Splitting schemes for unsteady problems involving the grad-div operator
Venue: arXiv cs.NA 2016
Year: 2016

In this paper we consider various splitting schemes for unsteady problems containing the grad-div operator. The fully implicit discretization of such problems would yield at each time step a linear problem that couples all components of the solution vector. In this paper we discuss various possibilities to decouple the equations for the different components that result in unconditionally stable schemes. If the spatial discretization uses Cartesian grids, the resulting schemes are Locally One Dimensional (LOD). The stability analysis of these schemes is based on the general stability theory of additive operator-difference schemes developed by Samarskii and his collaborators. The results of the theoretical analysis are illustrated on a 2D numerical example with a smooth manufactured solution.
COOLL: Controlled On/Off Loads Library, a Public Dataset of High-Sampled Electrical Signals for Appliance Identification
Venue: arXiv cs.OH 2016
Year: 2016

This paper gives a brief description of the Controlled On/Off Loads Library (COOLL) dataset. This latter is a dataset of high-sampled electrical current and voltage measurements representing individual appliances consumption. The measurements were taken in June 2016 in the PRISME laboratory of the University of Orléans, France. The appliances are mainly controllable appliances (i.e. we can precisely control their turn-on/off time instants). 42 appliances of 12 types were measured at a 100 kHz sampling frequency.
Maximizing the minimum achievable secrecy rate of two-way relay networks using the null space beamforming method
Venue: arXiv cs.IT 2016
Year: 2016

This paper concerns maximizing the minimum achievable secrecy rate of a two-way relay network in the presence of an eavesdropper, in which two nodes aim to exchange messages in two hops, using a multi-antenna relay. Throughout the first hop, the two nodes simultaneously transmit their messages to the relay. In the second hop, the relay broadcasts a combination of the received information to the users such that the transmitted signal lies in the null space of the eavesdropper's channel; this is called null space beamforming (NSBF). The best NSBF matrix for maximizing the minimum achievable secrecy rate is studied, showing that the problem is not convex in general. To address this issue, the problem is divided into three sub-problems: a close-to-optimal solution is derived by using the semi-definite relaxation (SDR) technique. Simulation results demonstrate the superiority of the proposed method w.r.t. the most well-known method addressed in the literature.
Parallelepipeds obtaining HBL lower bounds
Venue: arXiv cs.DS 2016
Year: 2016

This work studies the application of the discrete Holder-Brascamp-Lieb (HBL) inequalities to the design of communication optimal algorithms. In particular, it describes optimal tiling (blocking) strategies for nested loops that lack data dependencies and exhibit linear memory access patterns. We attain known lower bounds for communication costs by unraveling the relationship between the HBL linear program, its dual, and tile selection. The methods used are constructive and algorithmic. The case when all arrays have one index is explored in depth, as a useful example in which a particularly efficient tiling can be determined.
Hotelling-Downs Model with Limited Attraction
Venue: arXiv cs.GT 2016
Year: 2016

In this paper we study variations of the standard Hotelling-Downs model of spatial competition, where each agent attracts the clients in a restricted neighborhood, each client randomly picks one attractive agent for service. Two utility functions for agents are considered: support utility and winner utility. We generalize the results by Feldman et al. to the case where the clients are distributed arbitrarily. In the support utility setting, we show that a pure Nash equilibrium always exists by formulating the game as a potential game. In the winner utility setting, we show that there exists a Nash equilibrium in two cases: when there are at most 3 agents and when the size of attraction area is at least half of the entire space. We also consider the price of anarchy and the fairness of equilibria and give tight bounds on these criteria.
Word and Document Embeddings based on Neural Network Approaches
Venue: arXiv cs.CL 2016
Year: 2016

Data representation is a fundamental task in machine learning. The representation of data affects the performance of the whole machine learning system. In a long history, the representation of data is done by feature engineering, and researchers aim at designing better features for specific tasks. Recently, the rapid development of deep learning and representation learning has brought new inspiration to various domains. In natural language processing, the most widely used feature representation is the Bag-of-Words model. This model has the data sparsity problem and cannot keep the word order information. Other features such as part-of-speech tagging or more complex syntax features can only fit for specific tasks in most cases. This thesis focuses on word representation and document representation. We compare the existing systems and present our new model. First, for generating word embeddings, we make comprehensive comparisons among existing word embedding models. In terms of theory, we figure out the relationship between the two most important models, i.e., Skip-gram and GloVe. In our experiments, we analyze three key points in generating word embeddings, including the model construction, the training corpus and parameter design. We evaluate word embeddings with three types of tasks, and we argue that they cover the existing use of word embeddings. Through theory and practical experiments, we present some guidelines for how to generate a good word embedding. Second, in Chinese character or word representation. We introduce the joint training of Chinese character and word. ... Third, for document representation, we analyze the existing document representation models, including recursive NNs, recurrent NNs and convolutional NNs. We point out the drawbacks of these models and present our new model, the recurrent convolutional neural networks. ...
Rope through Loop Insertion for Robotic Knotting: A Virtual Magnetic Field Formulation
Venue: arXiv cs.RO 2016
Year: 2016

Inserting an end of a rope through a loop is a common and important action that is required for creating most types of knots. To perform this action, we need to pass the end of the rope through an area that is enclosed by another segment of rope. As for all knotting actions, the robot must for this exercise control over a semi-compliant and flexible body whose complex 3d shape is difficult to perceive and follow. Additionally, the target loop often deforms during the insertion. We address this problem by defining a virtual magnetic field through the loop's interior and use the Biot Savart law to guide the robotic manipulator that holds the end of the rope. This approach directly defines, for any manipulator position, a motion vector that results in a path that passes through the loop. The motion vector is directly derived from the position of the loop and changes as soon as it moves or deforms. In simulation, we test the insertion action against dynamic loop deformation of different intensity. We also combine insertion with grasp and release actions, coordinated by a hybrid control system, to tie knots in simulation and with a NAO robot.
NoiseOut: A Simple Way to Prune Neural Networks
Venue: arXiv cs.NE 2016
Year: 2016

Neural networks are usually over-parameterized with significant redundancy in the number of required neurons which results in unnecessary computation and memory usage at inference time. One common approach to address this issue is to prune these big networks by removing extra neurons and parameters while maintaining the accuracy. In this paper, we propose NoiseOut, a fully automated pruning algorithm based on the correlation between activations of neurons in the hidden layers. We prove that adding additional output neurons with entirely random targets results into a higher correlation between neurons which makes pruning by NoiseOut even more efficient. Finally, we test our method on various networks and datasets. These experiments exhibit high pruning rates while maintaining the accuracy of the original network.
A Bayesian approach to type-specific conic fitting
Venue: arXiv cs.CV 2016
Year: 2016

A perturbative approach is used to quantify the effect of noise in data points on fitted parameters in a general homogeneous linear model, and the results applied to the case of conic sections. There is an optimal choice of normalisation that minimises bias, and iteration with the correct reweighting significantly improves statistical reliability. By conditioning on an appropriate prior, an unbiased type-specific fit can be obtained. Error estimates for the conic coefficients may also be used to obtain both bias corrections and confidence intervals for other curve parameters.
Dynamic Resource Allocation in Next Generation Cellular Networks with Full-Duplex Self-backhauls
Venue: arXiv cs.NI 2016
Year: 2016

With the dense deployment of small cell networks, low-cost backhaul schemes for small cell base stations (SBSs) have attracted great attentions. Self-backhaul using cellular communication technology is considered as a promising solution. Although some excellent works have been done on self-backhaul in small cell networks, most of them do not consider the recent advances of full-duplex (FD) and massive multiple-input and multiple-output (MIMO) technologies. In this paper, we propose a self-backhaul scheme for small cell networks by combining FD and massive MIMO technologies. In our proposed scheme, the macro base station (MBS) is equipped with massive MIMO antennas, and the SBSs have the FD communication ability. By treating the SBSs as \textit{special} macro users, we can achieve the simultaneous transmissions of the access link of users and the backhaul link of SBSs in the same frequency. Furthermore, considering the existence of inter-tier and intra-tier interference, we formulate the power allocation problem of the MBS and SBSs as an optimization problem. Because the formulated power allocation problem is a non-convex problem, we transform the original problem into a difference of convex program (DCP) by successive convex approximation method (SCAM) and variable transformation, and then solve it using a constrained concave convex procedure (CCCP) based iterative algorithm. Finally, extensive simulations are conducted with different system configurations to verify the effectiveness of the proposed scheme.
The Explicit Definition of Quantifiers via Hilbert's epsilon is Confluent and Terminating
Venue: arXiv cs.LO 2016
Year: 2016

We investigate the elimination of quantifiers in first-order formulas via Hilbert's epsilon-operator (or -binder), following Bernays' explicit definitions of the existential and the universal quantifier symbol by means of epsilon-terms. This elimination has its first explicit occurrence in the proof of the first epsilon-theorem in Hilbert-Bernays in 1939. We think that there is a lacuna in this proof w.r.t. this elimination, related to the erroneous assumption that explicit definitions always terminate. Surprisingly, to the best of our knowledge, nobody ever proved confluence or termination for this elimination procedure. Even myths on non-confluence and the openness of the termination problem are circulating. We show confluence and termination of this elimination procedure by means of a direct, straightforward, and easily verifiable proof, based on a new theorem on how to obtain termination from weak normalization.
Deep Residual Learning for Compressed Sensing CT Reconstruction via Persistent Homology Analysis
Venue: arXiv cs.CV 2016
Year: 2016

Recently, compressed sensing (CS) computed tomography (CT) using sparse projection views has been extensively investigated to reduce the potential risk of radiation to patient. However, due to the insufficient number of projection views, an analytic reconstruction approach results in severe streaking artifacts and CS-based iterative approach is computationally very expensive. To address this issue, here we propose a novel deep residual learning approach for sparse view CT reconstruction. Specifically, based on a novel persistent homology analysis showing that the manifold of streaking artifacts is topologically simpler than original ones, a deep residual learning architecture that estimates the streaking artifacts is developed. Once a streaking artifact image is estimated, an artifact-free image can be obtained by subtracting the streaking artifacts from the input image. Using extensive experiments with real patient data set, we confirm that the proposed residual learning provides significantly better image reconstruction performance with several orders of magnitude faster computational speed.
A Survey of Credit Card Fraud Detection Techniques: Data and Technique Oriented Perspective
Venue: arXiv cs.CR 2016
Year: 2016

Credit card plays a very important rule in today's economy. It becomes an unavoidable part of household, business and global activities. Although using credit cards provides enormous benefits when used carefully and responsibly,significant credit and financial damages may be caused by fraudulent activities. Many techniques have been proposed to confront the growth in credit card fraud. However, all of these techniques have the same goal of avoiding the credit card fraud; each one has its own drawbacks, advantages and characteristics. In this paper, after investigating difficulties of credit card fraud detection, we seek to review the state of the art in credit card fraud detection techniques, data sets and evaluation criteria.The advantages and disadvantages of fraud detection methods are enumerated and compared.Furthermore, a classification of mentioned techniques into two main fraud detection approaches, namely, misuses (supervised) and anomaly detection (unsupervised) is presented. Again, a classification of techniques is proposed based on capability to process the numerical and categorical data sets. Different data sets used in literature are then described and grouped into real and synthesized data and the effective and common attributes are extracted for further usage.Moreover, evaluation employed criterions in literature are collected and discussed.Consequently, open issues for credit card fraud detection are explained as guidelines for new researchers.
A note about "Faster algorithms for computing Hong's bound on absolute positiveness" by K. Mehlhorn and S. Ray
Venue: arXiv cs.SC 2016
Year: 2016

We show that a linear-time algorithm for computing Hong's bound for positive roots of a univariate polynomial, described by K. Mehlhorn and S. Ray in an article "Faster algorithms for computing Hong's bound on absolute positiveness", is incorrect. We present a corrected version.
Wellformedness Properties in Euler Diagrams: An Eye Tracking Study for Visualisation Evaluation
Venue: arXiv cs.HC 2016
Year: 2016

In the field of information visualisation, Euler diagrams are an important tool used in various application areas such as engineering, medicine and social analysis. To effectively use Euler diagrams, some of the wellformedness properties needs to be avoided, as they are considered to reduce user comprehension. From the previous empirical studies, we know some properties are swappable but there is no clear justification which property would be the best to use. In this paper, we considered two main wellformedness properties (duplicated curve labels and disconnected zones) to test which among the two affect user comprehension the most, based on the task performance (accuracy and response time), preference and eye movements of the users. Twelve participants performed three different types of tasks with nine diagrams of each property (so, in total eighteen diagrams) and the results showed that duplicated curve labels property slows down and trigger extra eye movements, causing delays for the tasks. Though there is no significant difference in the accuracy but the insights obtained from the response time, preference and eye movements will be useful for software developers on the optimal way to visualise Euler diagrams in real world application areas.
Modeling Review Spam Using Temporal Patterns and Co-bursting Behaviors
Venue: arXiv cs.SI 2016
Year: 2016

Online reviews play a crucial role in helping consumers evaluate and compare products and services. However, review hosting sites are often targeted by opinion spamming. In recent years, many such sites have put a great deal of effort in building effective review filtering systems to detect fake reviews and to block malicious accounts. Thus, fraudsters or spammers now turn to compromise, purchase or even raise reputable accounts to write fake reviews. Based on the analysis of a real-life dataset from a review hosting site (dianping.com), we discovered that reviewers' posting rates are bimodal and the transitions between different states can be utilized to differentiate spammers from genuine reviewers. Inspired by these findings, we propose a two-mode Labeled Hidden Markov Model to detect spammers. Experimental results show that our model significantly outperforms supervised learning using linguistic and behavioral features in identifying spammers. Furthermore, we found that when a product has a burst of reviews, many spammers are likely to be actively involved in writing reviews to the product as well as to many other products. We then propose a novel co-bursting network for detecting spammer groups. The co-bursting network enables us to produce more accurate spammer groups than the current state-of-the-art reviewer-product (co-reviewing) network.
Trading information complexity for error
Venue: arXiv cs.CC 2016
Year: 2016

We consider the standard two-party communication model. The central problem studied in this article is how much one can save in information complexity by allowing an error of $ε$. For arbitrary functions, we obtain lower bounds and upper bounds indicating a gain that is of order $Ω(h(ε))$ and $O(h(\sqrtε))$. Here $h$ denotes the binary entropy function. We analyze the case of the two-bit AND function in detail to show that for this function the gain is $Θ(h(ε))$. This answers a question of [M. Braverman, A. Garg, D. Pankratov, and O. Weinstein, From information to exact communication (extended abstract), STOC'13]. We obtain sharp bounds for the set disjointness function of order $n$. For the case of the distributional error, we introduce a new protocol that achieves a gain of $Θ(\sqrt{h(ε)})$ provided that $n$ is sufficiently large. We apply these results to answer another of question of Braverman et al. regarding the randomized communication complexity of the set disjointness function. Answering a question of [Mark Braverman, Interactive information complexity, STOC'12], we apply our analysis of the set disjointness function to establish a gap between the two different notions of the prior-free information cost. This implies that amortized randomized communication complexity is not necessarily equal to the amortized distributional communication complexity with respect to the hardest distribution.