OpenRaiser/Intern-Atlas huggingface dataset:
MPC Validation and Aggregation of Unit Vectors
Venue: arXiv cs.CR 2017
Year: 2017

When dealing with privatized data, it is important to be able to protect against malformed user inputs. This becomes difficult in MPC systems as each server should not contain enough information to know what values any user has submitted. In this paper, we implement an MPC technique to verify blinded user inputs are unit vectors. In addition, we introduce a BGW circuit which can securely aggregate the blinded inputs while only releasing the result when it is above a public threshold. These distributed techniques take as input a unit vector. While this initially seems limiting compared to real number input, it is quite powerful for cases such as selecting from a list of options, indicating a location from a set of possibilities, or any system which uses one-hot encoding.
Deep Image Harmonization
Venue: arXiv cs.CV 2017
Year: 2017

Compositing is one of the most common operations in photo editing. To generate realistic composites, the appearances of foreground and background need to be adjusted to make them compatible. Previous approaches to harmonize composites have focused on learning statistical relationships between hand-crafted appearance features of the foreground and background, which is unreliable especially when the contents in the two layers are vastly different. In this work, we propose an end-to-end deep convolutional neural network for image harmonization, which can capture both the context and semantic information of the composite images during harmonization. We also introduce an efficient way to collect large-scale and high-quality training data that can facilitate the training process. Experiments on the synthesized dataset and real composite images show that the proposed network outperforms previous state-of-the-art methods.
Efficient Computation of Subspace Skyline over Categorical Domains
Venue: arXiv cs.DB 2017
Year: 2017

Platforms such as AirBnB, Zillow, Yelp, and related sites have transformed the way we search for accommodation, restaurants, etc. The underlying datasets in such applications have numerous attributes that are mostly Boolean or Categorical. Discovering the skyline of such datasets over a subset of attributes would identify entries that stand out while enabling numerous applications. There are only a few algorithms designed to compute the skyline over categorical attributes, yet are applicable only when the number of attributes is small. In this paper, we place the problem of skyline discovery over categorical attributes into perspective and design efficient algorithms for two cases. (i) In the absence of indices, we propose two algorithms, ST-S and ST-P, that exploits the categorical characteristics of the datasets, organizing tuples in a tree data structure, supporting efficient dominance tests over the candidate set. (ii) We then consider the existence of widely used precomputed sorted lists. After discussing several approaches, and studying their limitations, we propose TA-SKY, a novel threshold style algorithm that utilizes sorted lists. Moreover, we further optimize TA-SKY and explore its progressive nature, making it suitable for applications with strict interactive requirements. In addition to the extensive theoretical analysis of the proposed algorithms, we conduct a comprehensive experimental evaluation of the combination of real (including the entire AirBnB data collection) and synthetic datasets to study the practicality of the proposed algorithms. The results showcase the superior performance of our techniques, outperforming applicable approaches by orders of magnitude.
Joint Beamforming and Antenna Selection for Sum Rate Maximization in Cognitive Radio Networks
Venue: arXiv cs.IT 2017
Year: 2017

This letter studies joint transmit beamforming and antenna selection at a secondary base station (BS) with multiple primary users (PUs) in an underlay cognitive radio multiple-input single-output broadcast channel. The objective is to maximize the sum rate subject to the secondary BS transmit power, minimum required rates for secondary users, and PUs' interference power constraints. The utility function of interest is nonconcave and the involved constraints are nonconvex, so this problem is hard to solve. Nevertheless, we propose a new iterative algorithm that finds local optima at the least. We use an inner approximation method to construct and solve a simple convex quadratic program of moderate dimension at each iteration of the proposed algorithm. Simulation results indicate that the proposed algorithm converges quickly and outperforms existing approaches.
Robust Beamforming for Secrecy Rate in Cooperative Cognitive Radio Multicast Communications
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we propose a cooperative approach to improve the security of both primary and secondary systems in cognitive radio multicast communications. During their access to the frequency spectrum licensed to the primary users, the secondary unlicensed users assist the primary system in fortifying security by sending a jamming noise to the eavesdroppers, while simultaneously protect themselves from eavesdropping. The main objective of this work is to maximize the secrecy rate of the secondary system, while adhering to all individual primary users' secrecy rate constraints. In the case of passive eavesdroppers and imperfect channel state information knowledge at the transceivers, the utility function of interest is nonconcave and involved constraints are nonconvex, and thus, the optimal solutions are troublesome. To address this problem, we propose an iterative algorithm to arrive at a local optimum of the considered problem. The proposed iterative algorithm is guaranteed to achieve a Karush-Kuhn-Tucker solution.
Video transrating in AVC and HEVC transcoding
Venue: arXiv cs.MM 2017
Year: 2017

HEVC (MPEG-H Part 2 and H.265) is a new coding technology which is expected to be deployed on the market along with new video services in the near future. HEVC is a successor of currently widely used AVC (MPEG-4 Part 10 and H.264). In this paper, the quality coding gains obtained for the Cascaded Pixel Domain Transcoder of AVC-coded material to HEVC standard are reported. Extensive experiments showed that transcoding with bitrate reduction allows the achievement of better rate-distortion performance than by compressing an original video sequence with the use of AVC at the same (reduced) bitrate.
Occupancy Map Building through Bayesian Exploration
Venue: arXiv cs.RO 2017
Year: 2017

We propose a novel holistic approach for safe autonomous exploration and map building based on constrained Bayesian optimisation. This method finds optimal continuous paths instead of discrete sensing locations that inherently satisfy motion and safety constraints. Evaluating both the objective and constraints functions requires forward simulation of expected observations. As such evaluations are costly, the Bayesian optimiser proposes only paths which are likely to yield optimal results and satisfy the constraints with high confidence. By balancing the reward and risk associated with each path, the optimiser minimises the number of expensive function evaluations. We demonstrate the effectiveness of our approach in a series of experiments both in simulation and with a real ground robot and provide comparisons to other exploration techniques. Evidently, each method has its specific favourable conditions, where it outperforms all other techniques. Yet, by reasoning on the usefulness of the entire path instead of its end point, our method provides a robust and consistent performance through all tests and performs better than or as good as the other leading methods.
Learning A Physical Long-term Predictor
Venue: arXiv cs.AI 2017
Year: 2017

Evolution has resulted in highly developed abilities in many natural intelligences to quickly and accurately predict mechanical phenomena. Humans have successfully developed laws of physics to abstract and model such mechanical phenomena. In the context of artificial intelligence, a recent line of work has focused on estimating physical parameters based on sensory data and use them in physical simulators to make long-term predictions. In contrast, we investigate the effectiveness of a single neural network for end-to-end long-term prediction of mechanical phenomena. Based on extensive evaluation, we demonstrate that such networks can outperform alternate approaches having even access to ground-truth physical simulators, especially when some physical parameters are unobserved or not known a-priori. Further, our network outputs a distribution of outcomes to capture the inherent uncertainty in the data. Our approach demonstrates for the first time the possibility of making actionable long-term predictions from sensor data without requiring to explicitly model the underlying physical laws.
Human Eye Visual Hyperacuity: A New Paradigm for Sensing?
Venue: arXiv cs.CV 2017
Year: 2017

The human eye appears to be using a low number of sensors for image capturing. Furthermore, regarding the physical dimensions of cones-photoreceptors responsible for the sharp central vision-, we may realize that these sensors are of a relatively small size and area. Nonetheless, the eye is capable to obtain high resolution images due to visual hyperacuity and presents an impressive sensitivity and dynamic range when set against conventional digital cameras of similar characteristics. This article is based on the hypothesis that the human eye may be benefiting from diffraction to improve both image resolution and acquisition process. The developed method intends to explain and simulate using MATLAB software the visual hyperacuity: the introduction of a controlled diffraction pattern at an initial stage, enables the use of a reduced number of sensors for capturing the image and makes possible a subsequent processing to improve the final image resolution. The results have been compared with the outcome of an equivalent system but in absence of diffraction, achieving promising results. The main conclusion of this work is that diffraction could be helpful for capturing images or signals when a small number of sensors available, which is far from being a resolution-limiting factor.
Tracing Linguistic Relations in Winning and Losing Sides of Explicit Opposing Groups
Venue: arXiv cs.CL 2017
Year: 2017

Linguistic relations in oral conversations present how opinions are constructed and developed in a restricted time. The relations bond ideas, arguments, thoughts, and feelings, re-shape them during a speech, and finally build knowledge out of all information provided in the conversation. Speakers share a common interest to discuss. It is expected that each speaker's reply includes duplicated forms of words from previous speakers. However, linguistic adaptation is observed and evolves in a more complex path than just transferring slightly modified versions of common concepts. A conversation aiming a benefit at the end shows an emergent cooperation inducing the adaptation. Not only cooperation, but also competition drives the adaptation or an opposite scenario and one can capture the dynamic process by tracking how the concepts are linguistically linked. To uncover salient complex dynamic events in verbal communications, we attempt to discover self-organized linguistic relations hidden in a conversation with explicitly stated winners and losers. We examine open access data of the United States Supreme Court. Our understanding is crucial in big data research to guide how transition states in opinion mining and decision-making should be modeled and how this required knowledge to guide the model should be pinpointed, by filtering large amount of data.
Gradient Boosting on Stochastic Data Streams
Venue: arXiv cs.LG 2017
Year: 2017

Boosting is a popular ensemble algorithm that generates more powerful learners by linearly combining base models from a simpler hypothesis class. In this work, we investigate the problem of adapting batch gradient boosting for minimizing convex loss functions to online setting where the loss at each iteration is i.i.d sampled from an unknown distribution. To generalize from batch to online, we first introduce the definition of online weak learning edge with which for strongly convex and smooth loss functions, we present an algorithm, Streaming Gradient Boosting (SGB) with exponential shrinkage guarantees in the number of weak learners. We further present an adaptation of SGB to optimize non-smooth loss functions, for which we derive a O(ln N/N) convergence rate. We also show that our analysis can extend to adversarial online learning setting under a stronger assumption that the online weak learning edge will hold in adversarial setting. We finally demonstrate experimental results showing that in practice our algorithms can achieve competitive results as classic gradient boosting while using less computation.
Multidimensional Sampling of Isotropically Bandlimited Signals
Venue: arXiv cs.IT 2017
Year: 2017

A new lower bound on the average reconstruction error variance of multidimensional sampling and reconstruction is presented. It applies to sampling on arbitrary lattices in arbitrary dimensions, assuming a stochastic process with constant, isotropically bandlimited spectrum and reconstruction by the best linear interpolator. The lower bound is exact for any lattice at sufficiently high and low sampling rates. The two threshold rates where the error variance deviates from the lower bound gives two optimality criteria for sampling lattices. It is proved that at low rates, near the first threshold, the optimal lattice is the dual of the best sphere-covering lattice, which for the first time establishes a rigorous relation between optimal sampling and optimal sphere covering. A previously known result is confirmed at high rates, near the second threshold, namely, that the optimal lattice is the dual of the best sphere-packing lattice. Numerical results quantify the performance of various lattices for sampling and support the theoretical optimality criteria.
Reinforcement Learning for Pivoting Task
Venue: arXiv cs.RO 2017
Year: 2017

In this work we propose an approach to learn a robust policy for solving the pivoting task. Recently, several model-free continuous control algorithms were shown to learn successful policies without prior knowledge of the dynamics of the task. However, obtaining successful policies required thousands to millions of training episodes, limiting the applicability of these approaches to real hardware. We developed a training procedure that allows us to use a simple custom simulator to learn policies robust to the mismatch of simulation vs robot. In our experiments, we demonstrate that the policy learned in the simulator is able to pivot the object to the desired target angle on the real robot. We also show generalization to an object with different inertia, shape, mass and friction properties than those used during training. This result is a step towards making model-free reinforcement learning available for solving robotics tasks via pre-training in simulators that offer only an imprecise match to the real-world dynamics.
Truth and Regret in Online Scheduling
Venue: arXiv cs.GT 2017
Year: 2017

We consider a scheduling problem where a cloud service provider has multiple units of a resource available over time. Selfish clients submit jobs, each with an arrival time, deadline, length, and value. The service provider's goal is to implement a truthful online mechanism for scheduling jobs so as to maximize the social welfare of the schedule. Recent work shows that under a stochastic assumption on job arrivals, there is a single-parameter family of mechanisms that achieves near-optimal social welfare. We show that given any such family of near-optimal online mechanisms, there exists an online mechanism that in the worst case performs nearly as well as the best of the given mechanisms. Our mechanism is truthful whenever the mechanisms in the given family are truthful and prompt, and achieves optimal (within constant factors) regret. We model the problem of competing against a family of online scheduling mechanisms as one of learning from expert advice. A primary challenge is that any scheduling decisions we make affect not only the payoff at the current step, but also the resource availability and payoffs in future steps. Furthermore, switching from one algorithm (a.k.a. expert) to another in an online fashion is challenging both because it requires synchronization with the state of the latter algorithm as well as because it affects the incentive structure of the algorithms. We further show how to adapt our algorithm to a non-clairvoyant setting where job lengths are unknown until jobs are run to completion. Once again, in this setting, we obtain truthfulness along with asymptotically optimal regret (within poly-logarithmic factors).
PMLB: A Large Benchmark Suite for Machine Learning Evaluation and Comparison
Venue: arXiv cs.LG 2017
Year: 2017

The selection, development, or comparison of machine learning methods in data mining can be a difficult task based on the target problem and goals of a particular study. Numerous publicly available real-world and simulated benchmark datasets have emerged from different sources, but their organization and adoption as standards have been inconsistent. As such, selecting and curating specific benchmarks remains an unnecessary burden on machine learning practitioners and data scientists. The present study introduces an accessible, curated, and developing public benchmark resource to facilitate identification of the strengths and weaknesses of different machine learning methodologies. We compare meta-features among the current set of benchmark datasets in this resource to characterize the diversity of available data. Finally, we apply a number of established machine learning methods to the entire benchmark suite and analyze how datasets and algorithms cluster in terms of performance. This work is an important first step towards understanding the limitations of popular benchmarking suites and developing a resource that connects existing benchmarking standards to more diverse and efficient standards in the future.
Geohyperbolic Routing and Addressing Schemes
Venue: arXiv cs.NI 2017
Year: 2017

The key requirement to routing in any telecommunication network, and especially in Internet-of-Things (IoT) networks, is scalability. Routing must route packets between any source and destination in the network without incurring unmanageable routing overhead that grows quickly with increasing network size and dynamics. Here we present an addressing scheme and a coupled network topology design scheme that guarantee essentially optimal routing scalability. The FIB sizes are as small as they can be, equal to the number of adjacencies a node has, while the routing control overhead is minimized as nearly zero routing control messages are exchanged even upon catastrophic failures in the network. The key new ingredient is the addressing scheme, which is purely local, based only on geographic coordinates of nodes and a centrality measure, and does not require any sophisticated non-local computations or global network topology knowledge for network embedding. The price paid for these benefits is that network topology cannot be arbitrary but should follow a specific design, resulting in Internet-like topologies. The proposed schemes can be most easily deployed in overlay networks, and also in other network deployments, where geolocation information is available, and where network topology can grow following the design specifications.
In Search of an Entity Resolution OASIS: Optimal Asymptotic Sequential Importance Sampling
Venue: arXiv cs.LG 2017
Year: 2017

Entity resolution (ER) presents unique challenges for evaluation methodology. While crowdsourcing platforms acquire ground truth, sound approaches to sampling must drive labelling efforts. In ER, extreme class imbalance between matching and non-matching records can lead to enormous labelling requirements when seeking statistically consistent estimates for rigorous evaluation. This paper addresses this important challenge with the OASIS algorithm: a sampler and F-measure estimator for ER evaluation. OASIS draws samples from a (biased) instrumental distribution, chosen to ensure estimators with optimal asymptotic variance. As new labels are collected OASIS updates this instrumental distribution via a Bayesian latent variable model of the annotator oracle, to quickly focus on unlabelled items providing more information. We prove that resulting estimates of F-measure, precision, recall converge to the true population values. Thorough comparisons of sampling methods on a variety of ER datasets demonstrate significant labelling reductions of up to 83% without loss to estimate accuracy.
Introduction to Nonnegative Matrix Factorization
Venue: arXiv cs.NA 2017
Year: 2017

In this paper, we introduce and provide a short overview of nonnegative matrix factorization (NMF). Several aspects of NMF are discussed, namely, the application in hyperspectral imaging, geometry and uniqueness of NMF solutions, complexity, algorithms, and its link with extended formulations of polyhedra. In order to put NMF into perspective, the more general problem class of constrained low-rank matrix approximation problems is first briefly introduced.
Wireless Power Transfer for Distributed Estimation in Sensor Networks
Venue: arXiv cs.IT 2017
Year: 2017

This paper studies power allocation for distributed estimation of an unknown scalar random source in sensor networks with a multiple-antenna fusion center (FC), where wireless sensors are equipped with radio-frequency based energy harvesting technology. The sensors' observation is locally processed by using an uncoded amplify-and-forward scheme. The processed signals are then sent to the FC, and are coherently combined at the FC, at which the best linear unbiased estimator (BLUE) is adopted for reliable estimation. We aim to solve the following two power allocation problems: 1) minimizing distortion under various power constraints; and 2) minimizing total transmit power under distortion constraints, where the distortion is measured in terms of mean-squared error of the BLUE. Two iterative algorithms are developed to solve the non-convex problems, which converge at least to a local optimum. In particular, the above algorithms are designed to jointly optimize the amplification coefficients, energy beamforming, and receive filtering. For each problem, a suboptimal design, a single-antenna FC scenario, and a common harvester deployment for colocated sensors, are also studied. Using the powerful semidefinite relaxation framework, our result is shown to be valid for any number of sensors, each with different noise power, and for an arbitrarily number of antennas at the FC.
Peterson-Gorenstein-Zierler algorithm for skew RS codes
Venue: arXiv cs.IT 2017
Year: 2017

We design a non-commutative version of the Peterson-Gorenstein-Zierler decoding algorithm for a class of codes that we call skew RS codes. These codes are left ideals of a quotient of a skew polynomial ring, which endow them of a sort of non-commutative cyclic structure. Since we work over an arbitrary field, our techniques may be applied both to linear block codes and convolutional codes. In particular, our decoding algorithm applies for block codes beyond the classical cyclic case.