OpenRaiser/Intern-Atlas huggingface dataset:
Randomness Evaluation with the Discrete Fourier Transform Test Based on Exact Analysis of the Reference Distribution
Venue: arXiv cs.CR 2017
Year: 2017

In this paper, we study the problems in the discrete Fourier transform (DFT) test included in NIST SP 800-22 released by the National Institute of Standards and Technology (NIST), which is a collection of tests for evaluating both physical and pseudo-random number generators for cryptographic applications. The most crucial problem in the DFT test is that its reference distribution of the test statistic is not derived mathematically but rather numerically estimated, the DFT test for randomness is based on a pseudo-random number generator (PRNG). Therefore, the present DFT test should not be used unless the reference distribution is mathematically derived. Here, we prove that a power spectrum, which is a component of the test statistic, follows a chi-squared distribution with 2 degrees of freedom. Based on this fact, we propose a test whose reference distribution of the test statistic is mathematically derived. Furthermore, the results of testing non-random sequences and several PRNGs showed that the proposed test is more reliable and definitely more sensitive than the present DFT test.
Arimoto-Rényi Conditional Entropy and Bayesian $M$-ary Hypothesis Testing
Venue: arXiv cs.IT 2017
Year: 2017

This paper gives upper and lower bounds on the minimum error probability of Bayesian $M$-ary hypothesis testing in terms of the Arimoto-Rényi conditional entropy of an arbitrary order $α$. The improved tightness of these bounds over their specialized versions with the Shannon conditional entropy ($α=1$) is demonstrated. In particular, in the case where $M$ is finite, we show how to generalize Fano's inequality under both the conventional and list-decision settings. As a counterpart to the generalized Fano's inequality, allowing $M$ to be infinite, a lower bound on the Arimoto-Rényi conditional entropy is derived as a function of the minimum error probability. Explicit upper and lower bounds on the minimum error probability are obtained as a function of the Arimoto-Rényi conditional entropy for both positive and negative $α$. Furthermore, we give upper bounds on the minimum error probability as functions of the Rényi divergence. In the setup of discrete memoryless channels, we analyze the exponentially vanishing decay of the Arimoto-Rényi conditional entropy of the transmitted codeword given the channel output when averaged over a random coding ensemble.
MS and PAN image fusion by combining Brovey and wavelet methods
Venue: arXiv cs.CV 2017
Year: 2017

Among the existing fusion algorithms, the wavelet fusion method is the most frequently discussed one in recent publications because the wavelet approach preserves the spectral characteristics of the multispectral image better than other methods. The Brovey is also a popular fusion method used for its ability in preserving the spatial information of the PAN image. This study presents a new fusion approach that integrates the advantages of both the Brovey (which preserves a high degree of spatial information) and the wavelet (which preserves a high degree of spectral information) techniques to reduce the colour distortion of fusion results. Visual and statistical analyzes show that the proposed algorithm clearly improves the merging quality in terms of: correlation coefficient and UIQI; compared to fusion methods including, IHS, Brovey, PCA , HPF, discrete wavelet transform (DWT), and a-trous wavelet.
Multi-level Representations for Fine-Grained Typing of Knowledge Base Entities
Venue: arXiv cs.CL 2017
Year: 2017

Entities are essential elements of natural language. In this paper, we present methods for learning multi-level representations of entities on three complementary levels: character (character patterns in entity names extracted, e.g., by neural networks), word (embeddings of words in entity names) and entity (entity embeddings). We investigate state-of-the-art learning methods on each level and find large differences, e.g., for deep learning models, traditional ngram features and the subword model of fasttext (Bojanowski et al., 2016) on the character level; for word2vec (Mikolov et al., 2013) on the word level; and for the order-aware model wang2vec (Ling et al., 2015a) on the entity level. We confirm experimentally that each level of representation contributes complementary information and a joint representation of all three levels improves the existing embedding based baseline for fine-grained entity typing by a large margin. Additionally, we show that adding information from entity descriptions further improves multi-level representations of entities.
A Construction of Linear Codes and Their Complete Weight Enumerators
Venue: arXiv cs.IT 2017
Year: 2017

Recently, linear codes constructed from defining sets have been studied extensively. They may have nice parameters if the defining set is chosen properly. Let $ m >2$ be a positive integer. For an odd prime $ p $, let $ r=p^m $ and $\text{Tr}$ be the absolute trace function from $\mathbb{F}_r$ onto $\mathbb{F}_p$. In this paper, we give a construction of linear codes by defining the code $ C_{D}=\{(\mathrm{Tr}(ax))_{x\in D}: a \in \mathbb{F}_{r} \}, $ where $ D =\left\{x\in \mathbb{F}_{r} : \mathrm{Tr}(x)=1, \mathrm{Tr}(x^2)=0 \right\}. $ Its complete weight enumerator and weight enumerator are determined explicitly by employing cyclotomic numbers and Gauss sums. In addition, we obtain several optimal linear codes with a few weights. They have higher rate compared with other codes, which enables them to have essential applications in areas such as association schemes and secret sharing schemes.
On Achievable Rates of AWGN Energy-Harvesting Channels with Block Energy Arrival and Non-Vanishing Error Probabilities
Venue: arXiv cs.IT 2017
Year: 2017

This paper investigates the achievable rates of an additive white Gaussian noise (AWGN) energy-harvesting (EH) channel with an infinite battery. The EH process is characterized by a sequence of blocks of harvested energy, which is known causally at the source. The harvested energy remains constant within a block while the harvested energy across different blocks is characterized by a sequence of independent and identically distributed (i.i.d.) random variables. The blocks have length $L$, which can be interpreted as the coherence time of the energy arrival process. If $L$ is a constant or grows sublinearly in the blocklength $n$, we fully characterize the first-order term in the asymptotic expansion of the maximum transmission rate subject to a fixed tolerable error probability $\varepsilon$. The first-order term is known as the $\varepsilon$-capacity. In addition, we obtain lower and upper bounds on the second-order term in the asymptotic expansion, which reveal that the second order term scales as $\sqrt{\frac{L}{n}}$ for any $\varepsilon$ less than $1/2$. The lower bound is obtained through analyzing the save-and-transmit strategy. If $L$ grows linearly in $n$, we obtain lower and upper bounds on the $\varepsilon$-capacity, which coincide whenever the cumulative distribution function (cdf) of the EH random variable is continuous and strictly increasing. In order to achieve the lower bound, we have proposed a novel adaptive save-and-transmit strategy, which chooses different save-and-transmit codes across different blocks according to the energy variation across the blocks.
Greedy-Merge Degrading has Optimal Power-Law
Venue: arXiv cs.IT 2017
Year: 2017

Consider a channel with a given input distribution. Our aim is to degrade it to a channel with at most L output letters. One such degradation method is the so called "greedy-merge" algorithm. We derive an upper bound on the reduction in mutual information between input and output. For fixed input alphabet size and variable L, the upper bound is within a constant factor of an algorithm-independent lower bound. Thus, we establish that greedy-merge is optimal in the power-law sense.
Task-Specific Attentive Pooling of Phrase Alignments Contributes to Sentence Matching
Venue: arXiv cs.CL 2017
Year: 2017

This work studies comparatively two typical sentence matching tasks: textual entailment (TE) and answer selection (AS), observing that weaker phrase alignments are more critical in TE, while stronger phrase alignments deserve more attention in AS. The key to reach this observation lies in phrase detection, phrase representation, phrase alignment, and more importantly how to connect those aligned phrases of different matching degrees with the final classifier. Prior work (i) has limitations in phrase generation and representation, or (ii) conducts alignment at word and phrase levels by handcrafted features or (iii) utilizes a single framework of alignment without considering the characteristics of specific tasks, which limits the framework's effectiveness across tasks. We propose an architecture based on Gated Recurrent Unit that supports (i) representation learning of phrases of arbitrary granularity and (ii) task-specific attentive pooling of phrase alignments between two sentences. Experimental results on TE and AS match our observation and show the effectiveness of our approach.
Multiple Instance Hybrid Estimator for Learning Target Signatures
Venue: arXiv cs.CV 2017
Year: 2017

Signature-based detectors for hyperspectral target detection rely on knowing the specific target signature in advance. However, target signature are often difficult or impossible to obtain. Furthermore, common methods for obtaining target signatures, such as from laboratory measurements or manual selection from an image scene, usually do not capture the discriminative features of target class. In this paper, an approach for estimating a discriminative target signature from imprecise labels is presented. The proposed approach maximizes the response of the hybrid sub-pixel detector within a multiple instance learning framework and estimates a set of discriminative target signatures. After learning target signatures, any signature based detector can then be applied on test data. Both simulated and real hyperspectral target detection experiments are shown to illustrate the effectiveness of the method.
Information Pursuit: A Bayesian Framework for Sequential Scene Parsing
Venue: arXiv cs.CV 2017
Year: 2017

Despite enormous progress in object detection and classification, the problem of incorporating expected contextual relationships among object instances into modern recognition systems remains a key challenge. In this work we propose Information Pursuit, a Bayesian framework for scene parsing that combines prior models for the geometry of the scene and the spatial arrangement of objects instances with a data model for the output of high-level image classifiers trained to answer specific questions about the scene. In the proposed framework, the scene interpretation is progressively refined as evidence accumulates from the answers to a sequence of questions. At each step, we choose the question to maximize the mutual information between the new answer and the full interpretation given the current evidence obtained from previous inquiries. We also propose a method for learning the parameters of the model from synthesized, annotated scenes obtained by top-down sampling from an easy-to-learn generative scene model. Finally, we introduce a database of annotated indoor scenes of dining room tables, which we use to evaluate the proposed approach.
Son of Zorn's Lemma: Targeted Style Transfer Using Instance-aware Semantic Segmentation
Venue: arXiv cs.CV 2017
Year: 2017

Style transfer is an important task in which the style of a source image is mapped onto that of a target image. The method is useful for synthesizing derivative works of a particular artist or specific painting. This work considers targeted style transfer, in which the style of a template image is used to alter only part of a target image. For example, an artist may wish to alter the style of only one particular object in a target image without altering the object's general morphology or surroundings. This is useful, for example, in augmented reality applications (such as the recently released Pokemon GO), where one wants to alter the appearance of a single real-world object in an image frame to make it appear as a cartoon. Most notably, the rendering of real-world objects into cartoon characters has been used in a number of films and television show, such as the upcoming series Son of Zorn. We present a method for targeted style transfer that simultaneously segments and stylizes single objects selected by the user. The method uses a Markov random field model to smooth and anti-alias outlier pixels near object boundaries, so that stylized objects naturally blend into their surroundings.
Discovery, Retrieval, and Analysis of 'Star Wars' botnet in Twitter
Venue: arXiv cs.SI 2017
Year: 2017

It is known that many Twitter users are bots, which are accounts controlled and sometimes created by computers. Twitter bots can send spam tweets, manipulate public opinion and be used for online fraud. Here we report the discovery, retrieval, and analysis of the `Star Wars' botnet in Twitter, which consists of more than 350,000 bots tweeting random quotations exclusively from Star Wars novels. The botnet contains a single type of bot, showing exactly the same properties throughout the botnet. It is unusually large, many times larger than other available datasets. It provides a valuable source of ground truth for research on Twitter bots. We analysed and revealed rich details on how the botnet was designed and created. As of this writing, the Star Wars bots are still alive in Twitter. They have survived since their creation in 2013, despite the increasing efforts in recent years to detect and remove Twitter bots.We also reflect on the `unconventional' way in which we discovered the Star Wars bots, and discuss the current problems and future challenges of Twitter bot detection.
To Vote Before Decide: A Logless One-Phase Commit Protocol for Highly-Available Datastores
Venue: arXiv cs.DC 2017
Year: 2017

Highly-available datastores are widely deployed for online applications. However, many online applications are not contented with the simple data access interface currently provided by highly-available datastores. Distributed transaction support is demanded by applications such as large-scale online payment used by Alipay or Paypal. Current solutions to distributed transaction can spend more than half of the whole transaction processing time in distributed commit. An efficient atomic commit protocol is highly desirable. This paper presents the HACommit protocol, a logless one-phase commit protocol for highly-available systems. HACommit has transaction participants vote for a commit before the client decides to commit or abort the transaction; in comparison, the state-of-the-art practice for distributed commit is to have the client decide before participants vote. The change enables the removal of both the participant logging and the coordinator logging steps in the distributed commit process; it also makes possible that, after the client initiates the transaction commit, the transaction data is visible to other transactions within one communication roundtrip time (i.e., one phase). In the evaluation with extensive experiments, HACommit outperforms recent atomic commit solutions for highly-available datastores under different workloads. In the best case, HACommit can commit in one fifth of the time 2PC does.
Analysis and design of Raptor codes using a multi-edge framework
Venue: arXiv cs.IT 2017
Year: 2017

The focus of this paper is on the analysis and design of Raptor codes using a multi-edge framework. In this regard, we first represent the Raptor code as a multi-edge type low-density parity-check (METLDPC) code. This MET representation gives a general framework to analyze and design Raptor codes over a binary input additive white Gaussian noise channel using MET density evolution (MET-DE). We consider a joint decoding scheme based on the belief propagation (BP) decoding for Raptor codes in the multi-edge framework, and analyze the convergence behavior of the BP decoder using MET-DE. In joint decoding of Raptor codes, the component codes correspond to inner code and precode are decoded in parallel and provide information to each other. We also derive an exact expression for the stability of Raptor codes with joint decoding. We then propose an efficient Raptor code design method using the multi-edge framework, where we simultaneously optimize the inner code and the precode. Finally we consider performance-complexity trade-offs of Raptor codes using the multi-edge framework. Through density evolution analysis we show that the designed Raptor codes using the multi-edge framework outperform the existing Raptor codes in literature in terms of the realized rate.
Dynamic Complexity under Definable Changes
Venue: arXiv cs.LO 2017
Year: 2017

This paper studies dynamic complexity under definable change operations in the DynFO framework by Patnaik and Immerman. It is shown that for changes definable by parameter-free first-order formulas, all (uniform) $AC^1$ queries can be maintained by first-order dynamic programs. Furthermore, many maintenance results for single-tuple changes are extended to more powerful change operations: (1) The reachability query for undirected graphs is first-order maintainable under single tuple changes and first-order defined insertions, likewise the reachability query for directed acyclic graphs under quantifier-free insertions. (2) Context-free languages are first-order maintainable under $Σ_1$-defined changes. These results are complemented by several inexpressibility results, for example, that the reachability query cannot be maintained by quantifier-free programs under definable, quantifier-free deletions.
Network Topology Modulation for Energy and Data Transmission in Internet of Magneto-Inductive Things
Venue: arXiv cs.IT 2017
Year: 2017

Internet-of-things (IoT) architectures connecting a massive number of heterogeneous devices need energy efficient, low hardware complexity, low cost, simple and secure mechanisms to realize communication among devices. One of the emerging schemes is to realize simultaneous wireless information and power transfer (SWIPT) in an energy harvesting network. Radio frequency (RF) solutions require special hardware and modulation methods for RF to direct current (DC) conversion and optimized operation to achieve SWIPT which are currently in an immature phase. On the other hand, magneto-inductive (MI) communication transceivers are intrinsically energy harvesting with potential for SWIPT in an efficient manner. In this article, novel modulation and demodulation mechanisms are presented in a combined framework with multiple-access channel (MAC) communication and wireless power transmission. The network topology of power transmitting active coils in a transceiver composed of a grid of coils is changed as a novel method to transmit information. Practical demodulation schemes are formulated and numerically simulated for two-user MAC topology of small size coils. The transceivers are suitable to attach to everyday objects to realize reliable local area network (LAN) communication performances with tens of meters communication ranges. The designed scheme is promising for future IoT applications requiring SWIPT with energy efficient, low cost, low power and low hardware complexity solutions.
Modeling and Reasoning About Wireless Networks: A Graph-based Calculus Approach
Venue: arXiv cs.LO 2017
Year: 2017

We propose a graph-based process calculus for modeling and reasoning about wireless networks with local broadcasts. Graphs are used at syntactical level to describe the topological structures of networks. This calculus is equipped with a reduction semantics and a labelled transition semantics. The former is used to define weak barbed congruence. The latter is used to define a parameterized weak bisimulation emphasizing locations and local broadcasts. We prove that weak bisimilarity implies weak barbed congruence. The potential applications are illustrated by some examples and two case studies.
A Simple and Accurate Syntax-Agnostic Neural Model for Dependency-based Semantic Role Labeling
Venue: arXiv cs.CL 2017
Year: 2017

We introduce a simple and accurate neural model for dependency-based semantic role labeling. Our model predicts predicate-argument dependencies relying on states of a bidirectional LSTM encoder. The semantic role labeler achieves competitive performance on English, even without any kind of syntactic information and only using local inference. However, when automatically predicted part-of-speech tags are provided as input, it substantially outperforms all previous local models and approaches the best reported results on the English CoNLL-2009 dataset. We also consider Chinese, Czech and Spanish where our approach also achieves competitive results. Syntactic parsers are unreliable on out-of-domain data, so standard (i.e., syntactically-informed) SRL models are hindered when tested in this setting. Our syntax-agnostic model appears more robust, resulting in the best reported results on standard out-of-domain test sets.
Greed is Good: Optimistic Algorithms for Bipartite-Graph Partial Coloring on Multicore Architectures
Venue: arXiv cs.DC 2017
Year: 2017

In parallel computing, a valid graph coloring yields a lock-free processing of the colored tasks, data points, etc., without expensive synchronization mechanisms. However, coloring is not free and the overhead can be significant. In particular, for the bipartite-graph partial coloring (BGPC) and distance-2 graph coloring (D2GC) problems, which have various use-cases within the scientific computing and numerical optimization domains, the coloring overhead can be in the order of minutes with a single thread for many real-life graphs. In this work, we propose parallel algorithms for bipartite-graph partial coloring on shared-memory architectures. Compared to the existing shared-memory BGPC algorithms, the proposed ones employ greedier and more optimistic techniques that yield a better parallel coloring performance. In particular, on 16 cores, the proposed algorithms perform more than 4x faster than their counterparts in the ColPack library which is, to the best of our knowledge, the only publicly-available coloring library for multicore architectures. In addition to BGPC, the proposed techniques are employed to devise parallel distance-2 graph coloring algorithms and similar performance improvements have been observed. Finally, we propose two costless balancing heuristics for BGPC that can reduce the skewness and imbalance on the cardinality of color sets (almost) for free. The heuristics can also be used for the D2GC problem and in general, they will probably yield a better color-based parallelization performance especially on many-core architectures.