OpenRaiser/Intern-Atlas huggingface dataset:
Learning Optimal Redistribution Mechanisms through Neural Networks
Venue: arXiv cs.GT 2018
Year: 2018

We consider a setting where $p$ public resources are to be allocated among $n$ competing and strategic agents so as to maximize social welfare (the objects should be allocated to those who value them the most). This is called allocative efficiency (AE). We need the agents to report their valuations for obtaining these resources, truthfully referred to as dominant strategy incentive compatibility (DSIC). We use auction-based mechanisms to achieve AE and DSIC yet budget balance cannot be ensured, due to Green-Laffont Impossibility Theorem. That is, the net transfer of money cannot be zero. This problem has been addressed by designing a redistribution mechanism so as to ensure a minimum surplus of money as well as AE and DSIC. The objective could be to minimize surplus in expectation or in the worst case and these $p$ objects could be homogeneous or heterogeneous. Designing redistribution mechanisms which perform well in expectation becomes analytically challenging for heterogeneous settings. In this paper, we take a completely different, data-driven approach. We train a neural network to determine an optimal redistribution mechanism based on given settings with both the objectives, optimal in expectation and optimal in the worst case. We also propose a loss function to train a neural network to optimize worst case. We design neural networks with the underlying rebate functions being linear as well as nonlinear in terms of bids of the agents. Our networks' performances are same as the theoretical guarantees for the cases where it has been solved. We observe that a neural network based redistribution mechanism for homogeneous settings which uses nonlinear rebate functions outperforms linear rebate functions when the objective is optimal in expectation. Our approach also yields an optimal in expectation redistribution mechanism for heterogeneous settings.
Correlations and dynamics of consumption patterns in social-economic networks
Venue: arXiv cs.SI 2018
Year: 2018

We analyse a coupled dataset collecting the mobile phone communications and bank transactions history of a large number of individuals living in a Latin American country. After mapping the social structure and introducing indicators of socioeconomic status, demographic features, and purchasing habits of individuals we show that typical consumption patterns are strongly correlated with identified socioeconomic classes leading to patterns of stratification in the social structure. In addition we measure correlations between merchant categories and introduce a correlation network, which emerges with a meaningful community structure. We detect multivariate relations between merchant categories and show correlations in purchasing habits of individuals. Finally, by analysing individual consumption histories, we detect dynamical patterns in purchase behaviour and their correlations with the socioeconomic status, demographic characters and the egocentric social network of individuals. Our work provides novel and detailed insight into the relations between social and consuming behaviour with potential applications in resource allocation, marketing, and recommendation system design.
LEDAkem: a post-quantum key encapsulation mechanism based on QC-LDPC codes
Venue: arXiv cs.CR 2018
Year: 2018

This work presents a new code-based key encapsulation mechanism (KEM) called LEDAkem. It is built on the Niederreiter cryptosystem and relies on quasi-cyclic low-density parity-check codes as secret codes, providing high decoding speeds and compact keypairs. LEDAkem uses ephemeral keys to foil known statistical attacks, and takes advantage of a new decoding algorithm that provides faster decoding than the classical bit-flipping decoder commonly adopted in this kind of systems. The main attacks against LEDAkem are investigated, taking into account quantum speedups. Some instances of LEDAkem are designed to achieve different security levels against classical and quantum computers. Some performance figures obtained through an efficient C99 implementation of LEDAkem are provided.
Detecting Changes in Fully Polarimetric SAR Imagery with Statistical Information Theory
Venue: arXiv cs.IT 2018
Year: 2018

Images obtained from coherent illumination processes are contaminated with speckle. A prominent example of such imagery systems is the polarimetric synthetic aperture radar (PolSAR). For such remote sensing tool the speckle interference pattern appears in the form of a positive definite Hermitian matrix, which requires specialized models and makes change detection a hard task. The scaled complex Wishart distribution is a widely used model for PolSAR images. Such distribution is defined by two parameters: the number of looks and the complex covariance matrix. The last parameter contains all the necessary information to characterize the backscattered data and, thus, identifying changes in a sequence of images can be formulated as a problem of verifying whether the complex covariance matrices differ at two or more takes. This paper proposes a comparison between a classical change detection method based on the likelihood ratio and three statistical methods that depend on information-theoretic measures: the Kullback-Leibler distance and two entropies. The performance of these four tests was quantified in terms of their sample test powers and sizes using simulated data. The tests are then applied to actual PolSAR data. The results provide evidence that tests based on entropies may outperform those based on the Kullback-Leibler distance and likelihood ratio statistics.
Learning to Evade Static PE Machine Learning Malware Models via Reinforcement Learning
Venue: arXiv cs.CR 2018
Year: 2018

Machine learning is a popular approach to signatureless malware detection because it can generalize to never-before-seen malware families and polymorphic strains. This has resulted in its practical use for either primary detection engines or for supplementary heuristic detection by anti-malware vendors. Recent work in adversarial machine learning has shown that deep learning models are susceptible to gradient-based attacks, whereas non-differentiable models that report a score can be attacked by genetic algorithms that aim to systematically reduce the score. We propose a more general framework based on reinforcement learning (RL) for attacking static portable executable (PE) anti-malware engines. The general framework does not require a differentiable model nor does it require the engine to produce a score. Instead, an RL agent is equipped with a set of functionality-preserving operations that it may perform on the PE file. Through a series of games played against the anti-malware engine, it learns which sequences of operations are likely to result in evading the detector for any given malware sample. This enables completely black-box attacks against static PE anti-malware, and produces functional evasive malware samples as a direct result. We show in experiments that our method can attack a gradient-boosted machine learning model with evasion rates that are substantial and appear to be strongly dependent on the dataset. We demonstrate that attacks against this model appear to also evade components of publicly hosted antivirus engines. Adversarial training results are also presented: by retraining the model on evasive ransomware samples, a subsequent attack is 33% less effective. However, there are overfitting dangers when adversarial training, which we note. We release code to allow researchers to reproduce and improve this approach.
Oracle Separations for Quantum Statistical Zero-Knowledge
Venue: arXiv cs.CC 2018
Year: 2018

This paper investigates the power of quantum statistical zero knowledge interactive proof systems in the relativized setting. We prove the existence of an oracle relative to which quantum statistical zero-knowledge does not contain UP intersect coUP, and we prove that quantum statistical zero knowledge does not contain UP relative to a random oracle with probability 1. Our proofs of these statements rely on a bound on output state discrimination for relativized quantum circuits based on the quantum adversary method of Ambainis, following a technique similar to one used by Ben-David and Kothari to prove limitations on a query complexity variant of quantum statistical zero-knowledge.
Sequential Circuits from Regular Expressions Revisited
Venue: arXiv cs.FL 2018
Year: 2018

We revisit the long-neglected problem of sequential circuit constructions from regular expressions. The class of languages that are recognized by sequential circuits is equivalent to the class of regular languages. This fact is shown in [5] together with an inductive construction technique from regular expressions. In this note, we present an alternative algorithm, called the trigger-set approach, obtained by reversing well-known the follow-set approach to construct automata. We use our algorithm to obtain a regular expression matcher based on sequential circuits. Finally, we report our performance results in comparison with existing automata-based matchers.
Efficient Hierarchical Graph-Based Segmentation of RGBD Videos
Venue: arXiv cs.CV 2018
Year: 2018

We present an efficient and scalable algorithm for segmenting 3D RGBD point clouds by combining depth, color, and temporal information using a multistage, hierarchical graph-based approach. Our algorithm processes a moving window over several point clouds to group similar regions over a graph, resulting in an initial over-segmentation. These regions are then merged to yield a dendrogram using agglomerative clustering via a minimum spanning tree algorithm. Bipartite graph matching at a given level of the hierarchical tree yields the final segmentation of the point clouds by maintaining region identities over arbitrarily long periods of time. We show that a multistage segmentation with depth then color yields better results than a linear combination of depth and color. Due to its incremental processing, our algorithm can process videos of any length and in a streaming pipeline. The algorithm's ability to produce robust, efficient segmentation is demonstrated with numerous experimental results on challenging sequences from our own as well as public RGBD data sets.
Data-Driven Inversion-Based Control: closed-loop stability analysis for MIMO systems
Venue: arXiv cs.SY 2018
Year: 2018

Data-Driven Inversion-Based Control (D$^{2}$-IBC) is a recently introduced control design method for uncertain nonlinear systems, relying on a two degree-of-freedom architecture, with a nonlinear controller and a linear controller running in parallel. In this paper, extending to the MIMO case a previous result holding for the SISO case, we derive a finite-gain stability sufficient condition for a closed-loop system formed by a nonlinear MIMO plant, connected in feedback with a D$^{2}$-IBC controller.
A Two-point Method for PTZ Camera Calibration in Sports
Venue: arXiv cs.CV 2018
Year: 2018

Calibrating narrow field of view soccer cameras is challenging because there are very few field markings in the image. Unlike previous solutions, we propose a two-point method, which requires only two point correspondences given the prior knowledge of base location and orientation of a pan-tilt-zoom (PTZ) camera. We deploy this new calibration method to annotate pan-tilt-zoom data from soccer videos. The collected data are used as references for new images. We also propose a fast random forest method to predict pan-tilt angles without image-to-image feature matching, leading to an efficient calibration method for new images. We demonstrate our system on synthetic data and two real soccer datasets. Our two-point approach achieves superior performance over the state-of-the-art method.
Improving Word Vector with Prior Knowledge in Semantic Dictionary
Venue: arXiv cs.CL 2018
Year: 2018

Using low dimensional vector space to represent words has been very effective in many NLP tasks. However, it doesn't work well when faced with the problem of rare and unseen words. In this paper, we propose to leverage the knowledge in semantic dictionary in combination with some morphological information to build an enhanced vector space. We get an improvement of 2.3% over the state-of-the-art Heidel Time system in temporal expression recognition, and obtain a large gain in other name entity recognition (NER) tasks. The semantic dictionary Hownet alone also shows promising results in computing lexical similarity.
Variance-Optimal Offline and Streaming Stratified Random Sampling
Venue: arXiv cs.DB 2018
Year: 2018

Stratified random sampling (SRS) is a fundamental sampling technique that provides accurate estimates for aggregate queries using a small size sample, and has been used widely for approximate query processing. A key question in SRS is how to partition a target sample size among different strata. While Neyman allocation provides a solution that minimizes the variance of an estimate using this sample, it works under the assumption that each stratum is abundant, i.e., has a large number of data points to choose from. This assumption may not hold in general: one or more strata may be bounded, and may not contain a large number of data points, even though the total data size may be large. We first present VOILA, an offline method for allocating sample sizes to strata in a variance-optimal manner, even for the case when one or more strata may be bounded. We next consider SRS on streaming data that are continuously arriving. We show a lower bound, that any streaming algorithm for SRS must have (in the worst case) a variance that is Ω(r) factor away from the optimal, where r is the number of strata. We present S-VOILA, a practical streaming algorithm for SRS that is locally variance-optimal in its allocation of sample sizes to different strata. Our result from experiments on real and synthetic data show that VOILA can have significantly (1.4 to 50.0 times) smaller variance than Neyman allocation. The streaming algorithm S-VOILA results in a variance that is typically close to VOILA, which was given the entire input beforehand.
Quantitative Behavioural Reasoning for Higher-order Effectful Programs: Applicative Distances (Extended Version)
Venue: arXiv cs.LO 2018
Year: 2018

This paper studies the quantitative refinements of Abramsky's applicative similarity and bisimilarity in the context of a generalisation of Fuzz, a call-by-value $λ$-calculus with a linear type system that can express programs sensitivity, enriched with algebraic operations \emph{à la} Plotkin and Power. To do so a general, abstract framework for studying behavioural relations taking values over quantales is defined according to Lawvere's analysis of generalised metric spaces. Barr's notion of relator (or lax extension) is then extended to quantale-valued relations adapting and extending results from the field of monoidal topology. Abstract notions of quantale-valued effectful applicative similarity and bisimilarity are then defined and proved to be a compatible generalised metric (in the sense of Lawvere) and pseudometric, respectively, under mild conditions.
Using Additional Indexes for Fast Full-Text Search of Phrases That Contain Frequently Used Words
Venue: arXiv cs.IR 2018
Year: 2018

Searches for phrases and word sets in large text arrays by means of additional indexes are considered. Their use may reduce the query-processing time by an order of magnitude in comparison with standard inverted files.
Interactive Deep Colorization With Simultaneous Global and Local Inputs
Venue: arXiv cs.CV 2018
Year: 2018

Colorization methods using deep neural networks have become a recent trend. However, most of them do not allow user inputs, or only allow limited user inputs (only global inputs or only local inputs), to control the output colorful images. The possible reason is that it's difficult to differentiate the influence of different kind of user inputs in network training. To solve this problem, we present a novel deep colorization method, which allows simultaneous global and local inputs to better control the output colorized images. The key step is to design an appropriate loss function that can differentiate the influence of input data, global inputs and local inputs. With this design, our method accepts no inputs, or global inputs, or local inputs, or both global and local inputs, which is not supported in previous deep colorization methods. In addition, we propose a global color theme recommendation system to help users determine global inputs. Experimental results shows that our methods can better control the colorized images and generate state-of-art results.
On Scheduling Two-Stage Jobs on Multiple Two-Stage Flowshops
Venue: arXiv cs.DS 2018
Year: 2018

Motivated by the current research in data centers and cloud computing, we study the problem of scheduling a set of two-stage jobs on multiple two-stage flowshops. A new formulation for configurations of such scheduling is proposed, which leads directly to improvements to the complexity of scheduling algorithms for the problem. Motivated by the observation that the costs of the two stages can be significantly different, we present deeper study on the structures of the problem that leads to a new approach to designing scheduling algorithms for the problem. With more thorough analysis, we show that the new approach gives very significant improved scheduling algorithms for the problem when the costs of the two stages are different significantly. Improved approximation algorithms for the problem are also presented.
An Innovative Human-Robot Cognitive Coupling in Industrial Robot Control and Manufacturing
Venue: arXiv cs.RO 2018
Year: 2018

This paper demonstrates the groundwork for the structure and nature of Human-Robot Cognitive Coupling.The human mind is best at associating objects, while digital devices can only compare. Successful communication between robot and human agents involves translating human thought into unique numbers that can be compared, and translating these numbers back into a form that humans can understand. A cognitive robot is one capable of interpreting its own operational data. Working from a D&D project standpoint with a telerobot, a system is designed to utilize sensor data, extract usable profiles and information from them, and then apply them as a means of self-testing for nominal/off-nominal operations. If operations are considered off-nominal, the telerobot begins a sequence of recalling and comparing previous off-nominal occurrences to determine potential corrections. In this manner, a telerobot can apply previous 'experiences' in order to learn without the need for operator input. In the cognitive telerobotics, knowledge base is an important component to store required information. In this paper, a tool-centric knowledge base with learning capability is presented. In this paper, the knowledge can be updated based on the reinforcement learning algorithm at both global and local levels and knowledge fusion by coupling with operator's cognition.
An Energy Stable One-Field Fictitious Domain Method for Fluid-Structure Interactions
Venue: arXiv cs.CE 2018
Year: 2018

In this article, the energy stability of a one-field fictitious domain method is proved and validated by numerical tests in two and three dimensions. The distinguishing feature of this method is that it only solves for one velocity field for the whole fluid-structure domain; the interactions remain decoupled until solving the final linear algebraic equations. To achieve this the finite element procedures are carried out separately on two different meshes for the fluid and solid respectively, and the assembly of the final linear system brings the fluid and solid parts together via an isoparametric interpolation matrix between the two meshes. The weak formulations are introduced in the continuous case and after discretization in time. Then the stability is analyzed through an energy estimate. Finally, numerical examples are presented to validate the energy stability properties.
Liquid State Machine Learning for Resource and Cache Management in LTE-U Unmanned Aerial Vehicle (UAV) Networks
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, the problem of joint caching and resource allocation is investigated for a network of cache-enabled unmanned aerial vehicles (UAVs) that service wireless ground users over the LTE licensed and unlicensed (LTE-U) bands. The considered model focuses on users that can access both licensed and unlicensed bands while receiving contents from either the cache units at the UAVs directly or via content server-UAV-user links. This problem is formulated as an optimization problem which jointly incorporates user association, spectrum allocation, and content caching. To solve this problem, a distributed algorithm based on the machine learning framework of liquid state machine (LSM) is proposed. Using the proposed LSM algorithm, the cloud can predict the users' content request distribution while having only limited information on the network's and users' states. The proposed algorithm also enables the UAVs to autonomously choose the optimal resource allocation strategies that maximize the number of users with stable queues depending on the network states. Based on the users' association and content request distributions, the optimal contents that need to be cached at UAVs as well as the optimal resource allocation are derived. Simulation results using real datasets show that the proposed approach yields up to 33.3% and 50.3% gains, respectively, in terms of the number of users that have stable queues compared to two baseline algorithms: Q-learning with cache and Q-learning without cache. The results also show that LSM significantly improves the convergence time of up to 33.3% compared to conventional learning algorithms such as Q-learning.
Comparative Study of ECO and CFNet Trackers in Noisy Environment
Venue: arXiv cs.CV 2018
Year: 2018

Object tracking is one of the most challenging task and has secured significant attention of computer vision researchers in the past two decades. Recent deep learning based trackers have shown good performance on various tracking challenges. A tracking method should track objects in sequential frames accurately in challenges such as deformation, low resolution, occlusion, scale and light variations. Most trackers achieve good performance on specific challenges instead of all tracking problems, hence there is a lack of general purpose tracking algorithms that can perform well in all conditions. Moreover, performance of tracking techniques has not been evaluated in noisy environments. Visual object tracking has real world applications and there is good chance that noise may get added during image acquisition in surveillance cameras. We aim to study the robustness of two state of the art trackers in the presence of noise including Efficient Convolutional Operators (ECO) and Correlation Filter Network (CFNet). Our study demonstrates that the performance of these trackers degrades as the noise level increases, which demonstrate the need to design more robust tracking algorithms.