OpenRaiser/Intern-Atlas huggingface dataset:
Canonical Number and NutCracker: Heuristic Algorithms for the Graph Isomorphism Problem using Free Energy
Venue: arXiv cs.DS 2016
Year: 2016

This paper develops two heuristic algorithms to solve graph isomorphism, using free energy encoding. The first algorithm uses four types of encoding refinement techniques such that every graph can be distinguished by a canonical number computed by the algorithm. The second algorithm injects energy into the graph to conduct individualization such that the correspondence relation between a pair of isomorphic graphs can be found. The core principle behind the two algorithms is encoding discrete structures as real numbers. A large set of experiments demonstrated the effectiveness of our algorithms.
Transferability in Machine Learning: from Phenomena to Black-Box Attacks using Adversarial Samples
Venue: arXiv cs.CR 2016
Year: 2016

Many machine learning models are vulnerable to adversarial examples: inputs that are specially crafted to cause a machine learning model to produce an incorrect output. Adversarial examples that affect one model often affect another model, even if the two models have different architectures or were trained on different training sets, so long as both models were trained to perform the same task. An attacker may therefore train their own substitute model, craft adversarial examples against the substitute, and transfer them to a victim model, with very little information about the victim. Recent work has further developed a technique that uses the victim model as an oracle to label a synthetic training set for the substitute, so the attacker need not even collect a training set to mount the attack. We extend these recent techniques using reservoir sampling to greatly enhance the efficiency of the training procedure for the substitute model. We introduce new transferability attacks between previously unexplored (substitute, victim) pairs of machine learning model classes, most notably SVMs and decision trees. We demonstrate our attacks on two commercial machine learning classification systems from Amazon (96.19% misclassification rate) and Google (88.94%) using only 800 queries of the victim model, thereby showing that existing machine learning approaches are in general vulnerable to systematic black-box attacks regardless of their structure.
On Edge Caching in the Presence of Malicious Users
Venue: arXiv cs.IT 2016
Year: 2016

In this paper we investigate the problem of optimal cache placement in the presence of malicious mobile users in heterogeneous networks, where small-cell base stations are equipped with caches in order to reduce the overall backhaul load. In particular the malicious users aim at maximizing the congestion of files at the backhaul, i.e., at maximizing the average backhaul rate. For that adversarial model, we derive the achievable average backhaul rate of the heterogeneous network. Moreover, we study the system performance from a game-theoretic perspective, by naturally considering a zero-sum Stackelberg game between the macro-cell base station and the malicious users. We then thoroughly investigate the system performance in the presence of adversaries and we analyze the influence of the system parameters, such as the network topology and the capabilities of the small-cell base stations, on the overall performance of edge caching at the Stackelberg equilibrium. Our results highlight the impact of the malicious users on the overall caching performance of the network and they furthermore show the importance of an adversary-aware content placement at the small-cell base stations.
$χ$-bounded families of oriented graphs
Venue: arXiv cs.DM 2016
Year: 2016

A famous conjecture of Gyárfás and Sumner states for any tree $T$ and integer $k$, if the chromatic number of a graph is large enough, either the graph contains a clique of size $k$ or it contains $T$ as an induced subgraph. We discuss some results and open problems about extensions of this conjecture to oriented graphs. We conjecture that for every oriented star $S$ and integer $k$, if the chromatic number of a digraph is large enough, either the digraph contains a clique of size $k$ or it contains $S$ as an induced subgraph. As an evidence, we prove that for any oriented star $S$, every oriented graph with sufficiently large chromatic number contains either a transitive tournament of order $3$ or $S$ as an induced subdigraph. We then study for which sets ${\cal P}$ of orientations of $P_4$ (the path on four vertices) similar statements hold. We establish some positive and negative results.
Phase reconstruction of spectrograms based on a model of repeated audio events
Venue: arXiv cs.SD 2016
Year: 2016

Phase recovery of modified spectrograms is a major issue in audio signal processing applications, such as source separation. This paper introduces a novel technique for estimating the phases of components in complex mixtures within onset frames in the Time-Frequency (TF) domain. We propose to exploit the phase repetitions from one onset frame to another. We introduce a reference phase which characterizes a component independently of its activation times. The onset phases of a component are then modeled as the sum of this reference and an offset which is linearly dependent on the frequency. We derive a complex mixture model within onset frames and we provide two algorithms for the estimation of the model phase parameters. The model is estimated on experimental data and this technique is integrated into an audio source separation framework. The results demonstrate that this model is a promising tool for exploiting phase repetitions, and point out its potential for separating overlapping components in complex mixtures.
Optimal Deployment of Multistatic Radar System Using Multi-Objective Particle Swarm Optimization
Venue: arXiv cs.IT 2016
Year: 2016

We consider an optimization deployment problem of multistatic radar system (MSRS). Through the antenna placing and the transmitted power allocating, we optimally deploy the MSRS for two goals: 1) the first one is to improve the coverage ratio of surveillance region; 2) the second goal is to get a even distribution of signal energy in surveillance region. In two typical working modes of MSRS, we formulate the optimization problem by introducing two objective functions according to the two mentioned goals, respectively. Addressing on two main challenges of applying multi-objective particle swarm optimization (MOPSO) in solving the proposed optimization problem, we propose a deployment algorithm based on multiobjective particle swarm optimization with non-dominated relative crowding distance (MOPSO-NRCD). For the challenge of value difference, we propose a novel selection method with a non-dominated relative crowding distance. For the challenge of particle allocation, a multi-swarm structure of MOPSO is also introduced. Finally, simulation results are given out to prove the advantages and validity of the proposed deployment algorithm. It is shown that with same number of employed particles, the proposed MOPSO-NRCD algorithm can achieve better optimization performance than that of traditional multiobjective particle swarm optimization with crowding distance (MOPSO-CD).
On the Capacity Regions of Single-Channel and Multi-Channel Full-Duplex Links
Venue: arXiv cs.NI 2016
Year: 2016

We study the achievable capacity regions of full-duplex links in the single- and multi-channel cases (in the latter case, the channels are assumed to be orthogonal -- e.g., OFDM). We present analytical results that characterize the uplink and downlink capacity region and efficient algorithms for computing rate pairs at the region's boundary. We also provide near-optimal and heuristic algorithms that "convexify" the capacity region when it is not convex. The convexified region corresponds to a combination of a few full-duplex rates (i.e., to time sharing between different operation modes). The algorithms can be used for theoretical characterization of the capacity region as well as for resource (time, power, and channel) allocation with the objective of maximizing the sum of the rates when one of them (uplink or downlink) must be guaranteed (e.g., due to QoS considerations). We numerically illustrate the capacity regions and the rate gains (compared to time division duplex) for various channel and cancellation scenarios. The analytical results provide insights into the properties of the full-duplex capacity region and are essential for future development of scheduling, channel allocation, and power control algorithms.
Understanding the Smartrouter-based Peer CDN for Video Streaming
Venue: arXiv cs.MM 2016
Year: 2016

Recent years have witnessed a new video delivery paradigm: smartrouter-based video delivery network, which is enabled by smartrouters deployed at users' homes, together with the conventional video servers deployed in the datacenters. Recently, ChinaCache, a large content delivery network (CDN) provider, and Youku, a video service provider using smartrouters to assist video delivery, announced their cooperation to create a new paradigm of content delivery based on householders' network resources. This new paradigm is different from the conventional peer-to-peer (P2P) approach, because such dedicated smartrouters are inherently operated by the centralized video service providers in a coordinative manner. It is intriguing to study the strategies, performance and potential impact on the content delivery ecosystem of such peer CDN systems. In this paper, we study the Youku peer CDN, which has deployed over 300K smartrouter devices for its video streaming. In our measurement, 78K videos were investigated and 3TB traffic has been analyzed, over controlled routers and players. Our contributions are the following measurement insights. First, a global replication and caching strategy is essential for the peer CDN systems, and proactively scheduling replication and caching on a daily basis can guarantee their performance. Second, such peer CDN deployment can itself form an effective Quality of Service (QoS) monitoring sub-system, which can be used for fine-grained user request redirection. We also provide our analysis on the performance issues and potential improvements to the peer CDN systems.
Challenges in Mobile Multi-Device Ecosystems
Venue: arXiv cs.HC 2016
Year: 2016

Coordinated multi-display environments from the desktop, second-screen to gigapixel display walls are increasingly common. Personal and intimate mobile and wearable devices such as head-mounted displays, smartwatches, smartphones and tablets are rarely part of such multi-device ecosystems. With this paper, we contribute to a better understanding about factors that impede the creation and use of such mobile multi-device ecosystems. We base our findings on literature research and an expert survey. Specifically, we present grounded challenges relevant for the design, development and use of mobile multi-device environments.
Geometry-aware stationary subspace analysis
Venue: arXiv cs.LG 2016
Year: 2016

In many real-world applications data exhibits non-stationarity, i.e., its distribution changes over time. One approach to handling non-stationarity is to remove or minimize it before attempting to analyze the data. In the context of brain computer interface (BCI) data analysis this may be done by means of stationary subspace analysis (SSA). The classic SSA method finds a matrix that projects the data onto a stationary subspace by optimizing a cost function based on a matrix divergence. In this work we present an alternative method for SSA based on a symmetrized version of this matrix divergence. We show that this frames the problem in terms of distances between symmetric positive definite (SPD) matrices, suggesting a geometric interpretation of the problem. Stemming from this geometric viewpoint, we introduce and analyze a method which utilizes the geometry of the SPD matrix manifold and the invariance properties of its metrics. Most notably we show that these invariances alleviate the need to whiten the input matrices, a common step in many SSA methods which often introduces errors. We demonstrate the usefulness of our technique in experiments on both synthesized and real-world data.
Effective Blind Source Separation Based on the Adam Algorithm
Venue: arXiv cs.LG 2016
Year: 2016

In this paper, we derive a modified InfoMax algorithm for the solution of Blind Signal Separation (BSS) problems by using advanced stochastic methods. The proposed approach is based on a novel stochastic optimization approach known as the Adaptive Moment Estimation (Adam) algorithm. The proposed BSS solution can benefit from the excellent properties of the Adam approach. In order to derive the new learning rule, the Adam algorithm is introduced in the derivation of the cost function maximization in the standard InfoMax algorithm. The natural gradient adaptation is also considered. Finally, some experimental results show the effectiveness of the proposed approach.
Thinning, photonic beamsplitting, and a general discrete entropy power inequality
Venue: arXiv cs.IT 2016
Year: 2016

Many partially-successful attempts have been made to find the most natural discrete-variable version of Shannon's entropy power inequality (EPI). We develop an axiomatic framework from which we deduce the natural form of a discrete-variable EPI and an associated entropic monotonicity in a discrete-variable central limit theorem. In this discrete EPI, the geometric distribution, which has the maximum entropy among all discrete distributions with a given mean, assumes a role analogous to the Gaussian distribution in Shannon's EPI. The entropy power of $X$ is defined as the mean of a geometric random variable with entropy $H(X)$. The crux of our construction is a discrete-variable version of Lieb's scaled addition $X \boxplus_ηY$ of two discrete random variables $X$ and $Y$ with $η\in (0, 1)$. We discuss the relationship of our discrete EPI with recent work of Yu and Johnson who developed an EPI for a restricted class of random variables that have ultra-log-concave (ULC) distributions. Even though we leave open the proof of the aforesaid natural form of the discrete EPI, we show that this discrete EPI holds true for variables with arbitrary discrete distributions when the entropy power is redefined as $e^{H(X)}$ in analogy with the continuous version. Finally, we show that our conjectured discrete EPI is a special case of the yet-unproven Entropy Photon-number Inequality (EPnI), which assumes a role analogous to Shannon's EPI in capacity proofs for Gaussian bosonic (quantum) channels.
BattRAE: Bidimensional Attention-Based Recursive Autoencoders for Learning Bilingual Phrase Embeddings
Venue: arXiv cs.CL 2016
Year: 2016

In this paper, we propose a bidimensional attention based recursive autoencoder (BattRAE) to integrate clues and sourcetarget interactions at multiple levels of granularity into bilingual phrase representations. We employ recursive autoencoders to generate tree structures of phrases with embeddings at different levels of granularity (e.g., words, sub-phrases and phrases). Over these embeddings on the source and target side, we introduce a bidimensional attention network to learn their interactions encoded in a bidimensional attention matrix, from which we extract two soft attention weight distributions simultaneously. These weight distributions enable BattRAE to generate compositive phrase representations via convolution. Based on the learned phrase representations, we further use a bilinear neural model, trained via a max-margin method, to measure bilingual semantic similarity. To evaluate the effectiveness of BattRAE, we incorporate this semantic similarity as an additional feature into a state-of-the-art SMT system. Extensive experiments on NIST Chinese-English test sets show that our model achieves a substantial improvement of up to 1.63 BLEU points on average over the baseline.
Automatic Extraction of Causal Relations from Natural Language Texts: A Comprehensive Survey
Venue: arXiv cs.AI 2016
Year: 2016

Automatic extraction of cause-effect relationships from natural language texts is a challenging open problem in Artificial Intelligence. Most of the early attempts at its solution used manually constructed linguistic and syntactic rules on small and domain-specific data sets. However, with the advent of big data, the availability of affordable computing power and the recent popularization of machine learning, the paradigm to tackle this problem has slowly shifted. Machines are now expected to learn generic causal extraction rules from labelled data with minimal supervision, in a domain independent-manner. In this paper, we provide a comprehensive survey of causal relation extraction techniques from both paradigms, and analyse their relative strengths and weaknesses, with recommendations for future work.
Design of MLSD-Based Receivers for Short-Range Optical Communications Using the Volterra Expansion
Venue: arXiv cs.IT 2016
Year: 2016

Maximum Likelihood Sequence Detectors (MLSD) have been largely used to mitigate the Chromatic Dispersion (CD) in Intensity Modulation/Direct Detection (IM/DD) optical communication systems. For practical applications, the high complexity of the receivers remains an important issue. In this paper, we analyze the design of MLSD-based receivers using the Orthogonal Volterra Kernel Model for IM/DD optical communication systems in Metro Optical applications. We discuss the impact in complexity and performance of the main parameters of the model and provide three design options for the MLSDbased receiver. Finally we provide numerical simulations showing the Bit Error Rate (BER) performances of the three considered designs for both On-Off Keying (OOK) and higher order Pulse Amplitude Modulation (PAM).
Notes on Pervasive Virtuality
Venue: arXiv cs.HC 2016
Year: 2016

This paper summarizes current notes about a new mixed-reality paradigm that we named as "pervasive virtuality". This paradigm has emerged recently in industry and academia through different initiatives. In this paper we intend to explore this new area by proposing a set of features that we identified as important or helpful to realize pervasive virtuality in games and entertainment applications.
Real-Time Human Motion Capture with Multiple Depth Cameras
Venue: arXiv cs.CV 2016
Year: 2016

Commonly used human motion capture systems require intrusive attachment of markers that are visually tracked with multiple cameras. In this work we present an efficient and inexpensive solution to markerless motion capture using only a few Kinect sensors. Unlike the previous work on 3d pose estimation using a single depth camera, we relax constraints on the camera location and do not assume a co-operative user. We apply recent image segmentation techniques to depth images and use curriculum learning to train our system on purely synthetic data. Our method accurately localizes body parts without requiring an explicit shape model. The body joint locations are then recovered by combining evidence from multiple views in real-time. We also introduce a dataset of ~6 million synthetic depth frames for pose estimation from multiple cameras and exceed state-of-the-art results on the Berkeley MHAD dataset.
Visual BFI: an Exploratory Study for Image-based Personality Test
Venue: arXiv cs.HC 2016
Year: 2016

This paper positions and explores the topic of image-based personality test. Instead of responding to text-based questions, the subjects will be provided a set of "choose-your-favorite-image" visual questions. With the image options of each question belonging to the same concept, the subjects' personality traits are estimated by observing their preferences of images under several unique concepts. The solution to design such an image-based personality test consists of concept-question identification and image-option selection. We have presented a preliminary framework to regularize these two steps in this exploratory study. A demo version of the designed image-based personality test is available at http://www.visualbfi.org/. Subjective as well as objective evaluations have demonstrated the feasibility of image-based personality test in limited questions.
The Symbolic Interior Point Method
Venue: arXiv cs.AI 2016
Year: 2016

A recent trend in probabilistic inference emphasizes the codification of models in a formal syntax, with suitable high-level features such as individuals, relations, and connectives, enabling descriptive clarity, succinctness and circumventing the need for the modeler to engineer a custom solver. Unfortunately, bringing these linguistic and pragmatic benefits to numerical optimization has proven surprisingly challenging. In this paper, we turn to these challenges: we introduce a rich modeling language, for which an interior-point method computes approximate solutions in a generic way. While logical features easily complicates the underlying model, often yielding intricate dependencies, we exploit and cache local structure using algebraic decision diagrams (ADDs). Indeed, standard matrix-vector algebra is efficiently realizable in ADDs, but we argue and show that well-known optimization methods are not ideal for ADDs. Our engine, therefore, invokes a sophisticated matrix-free approach. We demonstrate the flexibility of the resulting symbolic-numeric optimizer on decision making and compressed sensing tasks with millions of non-zero entries.
Uniqueness of Minima of a Certain Least Squares Problem
Venue: arXiv cs.RO 2016
Year: 2016

This paper is essentially an exercise in studying the minima of a certain least squares optimization using the second partial derivative test. The motivation is to gain insight into an optimization-based solution to the problem of tracking human limbs using IMU sensors.
A Light-powered, Always-On, Smart Camera with Compressed Domain Gesture Detection
Venue: arXiv cs.CV 2016
Year: 2016

In this paper we propose an energy-efficient camera-based gesture recognition system powered by light energy for "always on" applications. Low energy consumption is achieved by directly extracting gesture features from the compressed measurements, which are the block averages and the linear combinations of the image sensor's pixel values. The gestures are recognized using a nearest-neighbour (NN) classifier followed by Dynamic Time Warping (DTW). The system has been implemented on an Analog Devices Black Fin ULP vision processor and powered by PV cells whose output is regulated by TI's DC-DC buck converter with Maximum Power Point Tracking (MPPT). Measured data reveals that with only 400 compressed measurements (768x compression ratio) per frame, the system is able to recognize key wake-up gestures with greater than 80% accuracy and only 95mJ of energy per frame. Owing to its fully self-powered operation, the proposed system can find wide applications in "always-on" vision systems such as in surveillance, robotics and consumer electronics with touch-less operation.
A resource-frugal probabilistic dictionary and applications in (meta)genomics
Venue: arXiv cs.DS 2016
Year: 2016

Genomic and metagenomic fields, generating huge sets of short genomic sequences, brought their own share of high performance problems. To extract relevant pieces of information from the huge data sets generated by current sequencing techniques, one must rely on extremely scalable methods and solutions. Indexing billions of objects is a task considered too expensive while being a fundamental need in this field. In this paper we propose a straightforward indexing structure that scales to billions of element and we propose two direct applications in genomics and metagenomics. We show that our proposal solves problem instances for which no other known solution scales-up. We believe that many tools and applications could benefit from either the fundamental data structure we provide or from the applications developed from this structure.