OpenRaiser/Intern-Atlas huggingface dataset:
Two Party Distribution Testing: Communication and Security
Venue: arXiv cs.DS 2018
Year: 2018

We study the problem of discrete distribution testing in the two-party setting. For example, in the standard closeness testing problem, Alice and Bob each have $t$ samples from, respectively, distributions $a$ and $b$ over $[n]$, and they need to test whether $a=b$ or $a,b$ are $ε$-far for some fixed $ε>0$. This is in contrast to the well-studied one-party case, where the tester has unrestricted access to samples of both distributions, for which optimal bounds are known for a number of variations. Despite being a natural constraint in applications, the two-party setting has evaded attention so far. We address two fundamental aspects: 1) what is the communication complexity, and 2) can it be accomplished securely, without Alice and Bob learning extra information about each other's input. Besides closeness testing, we also study the independence testing problem, where Alice and Bob have $t$ samples from distributions $a$ and $b$ respectively, which may be correlated; the question is whether $a,b$ are independent of $ε$-far from being independent. Our contribution is three-fold: 1) Communication: we show how to gain communication efficiency with more samples, beyond the information-theoretic bound on $t$. The gain is polynomially better than what one obtains by adapting standard algorithms. 2) Lower bounds: we prove tightness of our protocols for the closeness testing, and for the independence testing when the number of samples is unbounded. These lower bounds are of independent interest as these are the first 2-party communication lower bounds for testing problems. 3) Security: we define secure distribution testing and argue that it must leak at least some minimal information. We then provide secure versions of the above protocols with an overhead that is only polynomial in the security parameter.
Designing plateaued Boolean functions in spectral domain and their classification
Venue: arXiv cs.IT 2018
Year: 2018

The design of plateaued functions over $GF(2)^n$, also known as 3-valued Walsh spectra functions (taking the values from the set $\{0, \pm 2^{\lceil \frac{n+s}{2} \rceil}\}$), has been commonly approached by specifying a suitable algebraic normal form which then induces this particular Walsh spectral characterization. In this article, we consider the reversed design method which specifies these functions in the spectral domain by specifying a suitable allocation of the nonzero spectral values and their signs. We analyze the properties of trivial and nontrivial plateaued functions (as affine inequivalent distinct subclasses), which are distinguished by their Walsh support $S_f$ (the subset of $GF(2)^n$ having the nonzero spectral values) in terms of whether it is an affine subspace or not. The former class exactly corresponds to partially bent functions and admits linear structures, whereas the latter class may contain functions without linear structures. A simple sufficient condition on $S_f$, which ensures the nonexistence of linear structures, is derived and some generic design methods of nontrivial plateaued functions without linear structures are given. The extended affine equivalence of plateaued functions is also addressed using the concept of dual of plateaued functions. Furthermore, we solve the problem of specifying disjoint spectra (non)trivial plateaued functions of maximal cardinality whose concatenation can be used to construct bent functions in a generic manner. This approach may lead to new classes of bent functions due to large variety of possibilities to select underlying duals that define these disjoint spectra plateaued functions. An additional method of specifying affine inequivalent plateaued functions, obtained by applying a nonlinear transform to their input domain, is also given.
Image Cartoon-Texture Decomposition Using Isotropic Patch Recurrence
Venue: arXiv cs.CV 2018
Year: 2018

Aiming at separating the cartoon and texture layers from an image, cartoon-texture decomposition approaches resort to image priors to model cartoon and texture respectively. In recent years, patch recurrence has emerged as a powerful prior for image recovery. However, the existing strategies of using patch recurrence are ineffective to cartoon-texture decomposition, as both cartoon contours and texture patterns exhibit strong patch recurrence in images. To address this issue, we introduce the isotropy prior of patch recurrence, that the spatial configuration of similar patches in texture exhibits the isotropic structure which is different from that in cartoon, to model the texture component. Based on the isotropic patch recurrence, we construct a nonlocal sparsification system which can effectively distinguish well-patterned features from contour edges. Incorporating the constructed nonlocal system into morphology component analysis, we develop an effective method to both noiseless and noisy cartoon-texture decomposition. The experimental results have demonstrated the superior performance of the proposed method to the existing ones, as well as the effectiveness of the isotropic patch recurrence prior.
Multi-labeled Relation Extraction with Attentive Capsule Network
Venue: arXiv cs.CL 2018
Year: 2018

To disclose overlapped multiple relations from a sentence still keeps challenging. Most current works in terms of neural models inconveniently assuming that each sentence is explicitly mapped to a relation label, cannot handle multiple relations properly as the overlapped features of the relations are either ignored or very difficult to identify. To tackle with the new issue, we propose a novel approach for multi-labeled relation extraction with capsule network which acts considerably better than current convolutional or recurrent net in identifying the highly overlapped relations within an individual sentence. To better cluster the features and precisely extract the relations, we further devise attention-based routing algorithm and sliding-margin loss function, and embed them into our capsule network. The experimental results show that the proposed approach can indeed extract the highly overlapped features and achieve significant performance improvement for relation extraction comparing to the state-of-the-art works.
PerformanceNet: Score-to-Audio Music Generation with Multi-Band Convolutional Residual Network
Venue: arXiv cs.SD 2018
Year: 2018

Music creation is typically composed of two parts: composing the musical score, and then performing the score with instruments to make sounds. While recent work has made much progress in automatic music generation in the symbolic domain, few attempts have been made to build an AI model that can render realistic music audio from musical scores. Directly synthesizing audio with sound sample libraries often leads to mechanical and deadpan results, since musical scores do not contain performance-level information, such as subtle changes in timing and dynamics. Moreover, while the task may sound like a text-to-speech synthesis problem, there are fundamental differences since music audio has rich polyphonic sounds. To build such an AI performer, we propose in this paper a deep convolutional model that learns in an end-to-end manner the score-to-audio mapping between a symbolic representation of music called the piano rolls and an audio representation of music called the spectrograms. The model consists of two subnets: the ContourNet, which uses a U-Net structure to learn the correspondence between piano rolls and spectrograms and to give an initial result; and the TextureNet, which further uses a multi-band residual network to refine the result by adding the spectral texture of overtones and timbre. We train the model to generate music clips of the violin, cello, and flute, with a dataset of moderate size. We also present the result of a user study that shows our model achieves higher mean opinion score (MOS) in naturalness and emotional expressivity than a WaveNet-based model and two commercial sound libraries. We open our source code at https://github.com/bwang514/PerformanceNet
A Self-Learning Information Diffusion Model for Smart Social Networks
Venue: arXiv cs.SI 2018
Year: 2018

In this big data era, more and more social activities are digitized thereby becoming traceable, and thus the studies of social networks attract increasing attention from academia. It is widely believed that social networks play important role in the process of information diffusion. However, the opposite question, i.e., how does information diffusion process rebuild social networks, has been largely ignored. In this paper, we propose a new framework for understanding this reversing effect. Specifically, we first introduce a novel information diffusion model on social networks, by considering two types of individuals, i.e., smart and normal individuals, and two kinds of messages, true and false messages. Since social networks consist of human individuals, who have self-learning ability, in such a way that the trust of an individual to one of its neighbors increases (or decreases) if this individual received a true (or false) message from that neighbor. Based on such a simple self-learning mechanism, we prove that a social network can indeed become smarter, in terms of better distinguishing the true message from the false one. Moreover, we observe the emergence of social stratification based on the new model, i.e., the true messages initially posted by an individual closer to the smart one can be forwarded by more others, which is enhanced by the self-learning mechanism. We also find the crossover advantage, i.e., interconnection between two chain networks can make the related individuals possessing higher social influences, i.e., their messages can be forwarded by relatively more others. We obtained these results theoretically and validated them by simulations, which help better understand the reciprocity between social networks and information diffusion.
Multi-Temporal Resolution Convolutional Neural Networks for Acoustic Scene Classification
Venue: arXiv cs.SD 2018
Year: 2018

In this paper we present a Deep Neural Network architecture for the task of acoustic scene classification which harnesses information from increasing temporal resolutions of Mel-Spectrogram segments. This architecture is composed of separated parallel Convolutional Neural Networks which learn spectral and temporal representations for each input resolution. The resolutions are chosen to cover fine-grained characteristics of a scene's spectral texture as well as its distribution of acoustic events. The proposed model shows a 3.56% absolute improvement of the best performing single resolution model and 12.49% of the DCASE 2017 Acoustic Scenes Classification task baseline.
End-to-end Structure-Aware Convolutional Networks for Knowledge Base Completion
Venue: arXiv cs.AI 2018
Year: 2018

Knowledge graph embedding has been an active research topic for knowledge base completion, with progressive improvement from the initial TransE, TransH, DistMult et al to the current state-of-the-art ConvE. ConvE uses 2D convolution over embeddings and multiple layers of nonlinear features to model knowledge graphs. The model can be efficiently trained and scalable to large knowledge graphs. However, there is no structure enforcement in the embedding space of ConvE. The recent graph convolutional network (GCN) provides another way of learning graph node embedding by successfully utilizing graph connectivity structure. In this work, we propose a novel end-to-end Structure-Aware Convolutional Network (SACN) that takes the benefit of GCN and ConvE together. SACN consists of an encoder of a weighted graph convolutional network (WGCN), and a decoder of a convolutional network called Conv-TransE. WGCN utilizes knowledge graph node structure, node attributes and edge relation types. It has learnable weights that adapt the amount of information from neighbors used in local aggregation, leading to more accurate embeddings of graph nodes. Node attributes in the graph are represented as additional nodes in the WGCN. The decoder Conv-TransE enables the state-of-the-art ConvE to be translational between entities and relations while keeps the same link prediction performance as ConvE. We demonstrate the effectiveness of the proposed SACN on standard FB15k-237 and WN18RR datasets, and it gives about 10% relative improvement over the state-of-the-art ConvE in terms of HITS@1, HITS@3 and HITS@10.
SD-WAN Threat Landscape
Venue: arXiv cs.CR 2018
Year: 2018

Software Defined Wide Area Network (SD-WAN or SDWAN) is a modern conception and an attractive trend in network technologies. SD-WAN is defined as a specific application of software-defined networking (SDN) to WAN connections. There is growing recognition that SDN and SD-WAN technologies not only expand features, but also expose new vulnerabilities. Unfortunately, at the present time, most vendors say that SD-WAN are perfectly safe, hardened, and fully protected. The goal of this paper is to understand SD-WAN threats using practical approach. We describe basic SD-WAN features and components, investigate an attack surface, explore various vendor features and their security, explain threats and vulnerabilities found in SD-WAN products. We also extend existing SDN threat models by describing new potential threats and attack vectors, provide examples, and consider high-level approaches for their mitigations. The provided results may be used by SD-WAN developers as a part of Secure Software Development Life Cycle (SSDLC), security researchers for penetration testing and vulnerability assessment, system integrators for secure design of SD-WAN solutions, and finally customers for secure deployment operations and configurations of SD-WAN enabled network. The main idea of this work is that SD-WAN threat model involves all traditional network and SDN threats, as well as new product-specific threats, appended by vendors which reinvent or introduce proprietary technologies immature from a security perspective.
New Theoretical Bounds and Constructions of Permutation Codes under Block Permutation Metric
Venue: arXiv cs.IT 2018
Year: 2018

Permutation codes under different metrics have been extensively studied due to their potentials in various applications. Generalized Cayley metric is introduced to correct generalized transposition errors, including previously studied metrics such as Kendall's $τ$-metric, Ulam metric and Cayley metric as special cases. Since the generalized Cayley distance between two permutations is not easily computable, Yang et al. introduced a related metric of the same order, named the block permutation metric. Given positive integers $n$ and $d$, let $\mathcal{C}_{B}(n,d)$ denote the maximum size of a permutation code in $S_n$ with minimum block permutation distance $d$. In this paper, we focus on the theoretical bounds of $\mathcal{C}_{B}(n,d)$ and the constructions of permutation codes under block permutation metric. Using a graph theoretic approach, we improve the Gilbert-Varshamov type bound by a factor of $Ω(\log{n})$, when $d$ is fixed and $n$ goes into infinity. We also propose a new encoding scheme based on binary constant weight codes. Moreover, an upper bound beating the sphere-packing type bound is given when $d$ is relatively close to $n$.
Streaming Hardness of Unique Games
Venue: arXiv cs.CC 2018
Year: 2018

We study the problem of approximating the value of a Unique Game instance in the streaming model. A simple count of the number of constraints divided by $p$, the alphabet size of the Unique Game, gives a trivial $p$-approximation that can be computed in $O(\log n)$ space. Meanwhile, with high probability, a sample of $\tilde{O}(n)$ constraints suffices to estimate the optimal value to $(1+ε)$ accuracy. We prove that any single-pass streaming algorithm that achieves a $(p-ε)$-approximation requires $Ω_ε(\sqrt{n})$ space. Our proof is via a reduction from lower bounds for a communication problem that is a $p$-ary variant of the Boolean Hidden Matching problem studied in the literature. Given the utility of Unique Games as a starting point for reduction to other optimization problems, our strong hardness for approximating Unique Games could lead to down\emph{stream} hardness results for streaming approximability for other CSP-like problems.
Newton: A Language for Describing Physics
Venue: arXiv cs.PL 2018
Year: 2018

This article introduces Newton, a specification language for notating the analytic form, units of measure, and sensor signal properties for physical-object-specific invariants and general physical laws. We designed Newton to provide a means for hardware designers (e.g., sensor integrated circuit manufacturers, computing hardware architects, or mechanical engineers) to specify properties of the physical environments in which embedded computing systems will be deployed (e.g., a sensing platform deployed on a bridge versus worn by a human). Compilers and other program analysis tools for embedded systems can use a library interface to the Newton compiler to obtain information about the sensors, sensor signals, and inter-signal relationships imposed by the structure and materials properties of a given physical system. The information encoded within Newton specifications could enable new compile-time transformations that exploit information about the physical world.
Design of Low Complexity GFDM Transceiver
Venue: arXiv cs.IT 2018
Year: 2018

In this work, we propose a novel low complexity Generalised Frequency Division Multiplexing (GFDM) transceiver design. GFDM modulation matrix is factorized into FFT matrices and a diagonal matrix to design low complexity GFDM transmitter. Factorization of GFDM modulation matrix is used to derive low complexity Matched Filter (MF), Zero Forcing (ZF) and Minimum Mean Square Error (MMSE) based novel low complexity self-interference equalizers. A two-stage receiver is proposed for multipath fading channel in which channel equalization is followed by our proposed low-complexity self-interference equalizers. Unlike other known low complexity GFDM transceivers, our proposed transceiver attains low complexity for arbitrary number of time and frequency slots. The complexity of our proposed transceiver is log-linear with a number of transmitted symbols and achieves 3 to 300 times lower complexity compared to the existing structures without incurring any performance loss. Our proposed Unbiased-MMSE receiver outperforms our proposed ZF receiver without any significant increase in complexity especially in the case of large number of time slots. In a nutshell, our proposed transceiver enables low complexity flexible GFDM transceiver implementation.
A Deep Ensemble Framework for Fake News Detection and Classification
Venue: arXiv cs.CL 2018
Year: 2018

Fake news, rumor, incorrect information, and misinformation detection are nowadays crucial issues as these might have serious consequences for our social fabrics. The rate of such information is increasing rapidly due to the availability of enormous web information sources including social media feeds, news blogs, online newspapers etc. In this paper, we develop various deep learning models for detecting fake news and classifying them into the pre-defined fine-grained categories. At first, we develop models based on Convolutional Neural Network (CNN) and Bi-directional Long Short Term Memory (Bi-LSTM) networks. The representations obtained from these two models are fed into a Multi-layer Perceptron Model (MLP) for the final classification. Our experiments on a benchmark dataset show promising results with an overall accuracy of 44.87\%, which outperforms the current state of the art.
CUNI System for the WMT18 Multimodal Translation Task
Venue: arXiv cs.CL 2018
Year: 2018

We present our submission to the WMT18 Multimodal Translation Task. The main feature of our submission is applying a self-attentive network instead of a recurrent neural network. We evaluate two methods of incorporating the visual features in the model: first, we include the image representation as another input to the network; second, we train the model to predict the visual features and use it as an auxiliary objective. For our submission, we acquired both textual and multimodal additional data. Both of the proposed methods yield significant improvements over recurrent networks and self-attentive textual baselines.
Learning data augmentation policies using augmented random search
Venue: arXiv cs.LG 2018
Year: 2018

Previous attempts for data augmentation are designed manually, and the augmentation policies are dataset-specific. Recently, an automatic data augmentation approach, named AutoAugment, is proposed using reinforcement learning. AutoAugment searches for the augmentation polices in the discrete search space, which may lead to a sub-optimal solution. In this paper, we employ the Augmented Random Search method (ARS) to improve the performance of AutoAugment. Our key contribution is to change the discrete search space to continuous space, which will improve the searching performance and maintain the diversities between sub-policies. With the proposed method, state-of-the-art accuracies are achieved on CIFAR-10, CIFAR-100, and ImageNet (without additional data). Our code is available at https://github.com/gmy2013/ARS-Aug.
Syntax Helps ELMo Understand Semantics: Is Syntax Still Relevant in a Deep Neural Architecture for SRL?
Venue: arXiv cs.CL 2018
Year: 2018

Do unsupervised methods for learning rich, contextualized token representations obviate the need for explicit modeling of linguistic structure in neural network models for semantic role labeling (SRL)? We address this question by incorporating the massively successful ELMo embeddings (Peters et al., 2018) into LISA (Strubell et al., 2018), a strong, linguistically-informed neural network architecture for SRL. In experiments on the CoNLL-2005 shared task we find that though ELMo out-performs typical word embeddings, beginning to close the gap in F1 between LISA with predicted and gold syntactic parses, syntactically-informed models still out-perform syntax-free models when both use ELMo, especially on out-of-domain data. Our results suggest that linguistic structures are indeed still relevant in this golden age of deep learning for NLP.
Mathematical Theory of Evidence Versus Evidence
Venue: arXiv cs.AI 2018
Year: 2018

This paper is concerned with the apparent greatest weakness of the Mathematical Theory of Evidence (MTE) of Shafer \cite{Shafer:76}, which has been strongly criticized by Wasserman \cite{Wasserman:92ijar}. Weaknesses of Shafer's proposal \cite{Shafer:90b} of probabilistic interpretation of MTE belief functions is demonstrated. Thereafter a new probabilistic interpretation of MTE conforming both to definition of belief function and to Dempster's rule of combination of independent evidence. It is shown that shaferian conditioning of belief functions on observations \cite{Shafer:90b} may be treated as selection combined with modification of data, that is data is not viewed as it is but it is casted into one's beliefs in what it should be like.