OpenRaiser/Intern-Atlas huggingface dataset:
Non-linear maximum rank distance codes in the cyclic model for the field reduction of finite geometries
Venue: arXiv cs.IT 2017
Year: 2017

In this paper we construct infinite families of non-linear maximum rank distance codes by using the setting of bilinear forms of a finite vector space. We also give a geometric description of such codes by using the cyclic model for the field reduction of finite geometries and we show that these families contain the non-linear maximum rank distance codes recently provided by Cossidente, Marino and Pavese.
A Fine-Grained Hierarchy of Hard Problems in the Separated Fragment
Venue: arXiv cs.LO 2017
Year: 2017

Recently, the separated fragment (SF) has been introduced and proved to be decidable. Its defining principle is that universally and existentially quantified variables may not occur together in atoms. The known upper bound on the time required to decide SF's satisfiability problem is formulated in terms of quantifier alternations: Given an SF sentence $\exists \vec{z} \forall \vec{x}_1 \exists \vec{y}_1 \ldots \forall \vec{x}_n \exists \vec{y}_n . ψ$ in which $ψ$ is quantifier free, satisfiability can be decided in nondeterministic $n$-fold exponential time. In the present paper, we conduct a more fine-grained analysis of the complexity of SF-satisfiability. We derive an upper and a lower bound in terms of the degree of interaction of existential variables (short: degree)}---a novel measure of how many separate existential quantifier blocks in a sentence are connected via joint occurrences of variables in atoms. Our main result is the $k$-NEXPTIME-completeness of the satisfiability problem for the set $SF_{\leq k}$ of all SF sentences that have degree $k$ or smaller. Consequently, we show that SF-satisfiability is non-elementary in general, since SF is defined without restrictions on the degree. Beyond trivial lower bounds, nothing has been known about the hardness of SF-satisfiability so far.
The Meaning Factory at SemEval-2017 Task 9: Producing AMRs with Neural Semantic Parsing
Venue: arXiv cs.CL 2017
Year: 2017

We evaluate a semantic parser based on a character-based sequence-to-sequence model in the context of the SemEval-2017 shared task on semantic parsing for AMRs. With data augmentation, super characters, and POS-tagging we gain major improvements in performance compared to a baseline character-level model. Although we improve on previous character-based neural semantic parsing models, the overall accuracy is still lower than a state-of-the-art AMR parser. An ensemble combining our neural semantic parser with an existing, traditional parser, yields a small gain in performance.
ReLayNet: Retinal Layer and Fluid Segmentation of Macular Optical Coherence Tomography using Fully Convolutional Network
Venue: arXiv cs.CV 2017
Year: 2017

Optical coherence tomography (OCT) is used for non-invasive diagnosis of diabetic macular edema assessing the retinal layers. In this paper, we propose a new fully convolutional deep architecture, termed ReLayNet, for end-to-end segmentation of retinal layers and fluid masses in eye OCT scans. ReLayNet uses a contracting path of convolutional blocks (encoders) to learn a hierarchy of contextual features, followed by an expansive path of convolutional blocks (decoders) for semantic segmentation. ReLayNet is trained to optimize a joint loss function comprising of weighted logistic regression and Dice overlap loss. The framework is validated on a publicly available benchmark dataset with comparisons against five state-of-the-art segmentation methods including two deep learning based approaches to substantiate its effectiveness.
Semi-Latent GAN: Learning to generate and modify facial images from attributes
Venue: arXiv cs.CV 2017
Year: 2017

Generating and manipulating human facial images using high-level attributal controls are important and interesting problems. The models proposed in previous work can solve one of these two problems (generation or manipulation), but not both coherently. This paper proposes a novel model that learns how to both generate and modify the facial image from high-level semantic attributes. Our key idea is to formulate a Semi-Latent Facial Attribute Space (SL-FAS) to systematically learn relationship between user-defined and latent attributes, as well as between those attributes and RGB imagery. As part of this newly formulated space, we propose a new model --- SL-GAN which is a specific form of Generative Adversarial Network. Finally, we present an iterative training algorithm for SL-GAN. The experiments on recent CelebA and CASIA-WebFace datasets validate the effectiveness of our proposed framework. We will also make data, pre-trained models and code available.
Clothing and People - A Social Signal Processing Perspective
Venue: arXiv cs.CV 2017
Year: 2017

In our society and century, clothing is not anymore used only as a means for body protection. Our paper builds upon the evidence, studied within the social sciences, that clothing brings a clear communicative message in terms of social signals, influencing the impression and behaviour of others towards a person. In fact, clothing correlates with personality traits, both in terms of self-assessment and assessments that unacquainted people give to an individual. The consequences of these facts are important: the influence of clothing on the decision making of individuals has been investigated in the literature, showing that it represents a discriminative factor to differentiate among diverse groups of people. Unfortunately, this has been observed after cumbersome and expensive manual annotations, on very restricted populations, limiting the scope of the resulting claims. With this position paper, we want to sketch the main steps of the very first systematic analysis, driven by social signal processing techniques, of the relationship between clothing and social signals, both sent and perceived. Thanks to human parsing technologies, which exhibit high robustness owing to deep learning architectures, we are now capable to isolate visual patterns characterising a large types of garments. These algorithms will be used to capture statistical relations on a large corpus of evidence to confirm the sociological findings and to go beyond the state of the art.
What Constitutes Peer Review of Data: A survey of published peer review guidelines
Venue: arXiv cs.DL 2017
Year: 2017

Since a number of journals specifically focus on the review and publication of data sets, reviewing their policies seems an appropriate place to start in assessing what existing practice looks like in the 'real world' of reviewing and publishing data. This article outlines a study of the publicly available peer review policies of 39 scientific publications that publish data papers to discern which criteria are most and least frequently referenced. It also compares current practice with proposed criteria published in 2012.
It Takes (Only) Two: Adversarial Generator-Encoder Networks
Venue: arXiv cs.CV 2017
Year: 2017

We present a new autoencoder-type architecture that is trainable in an unsupervised mode, sustains both generation and inference, and has the quality of conditional and unconditional samples boosted by adversarial learning. Unlike previous hybrids of autoencoders and adversarial networks, the adversarial game in our approach is set up directly between the encoder and the generator, and no external mappings are trained in the process of learning. The game objective compares the divergences of each of the real and the generated data distributions with the prior distribution in the latent space. We show that direct generator-vs-encoder game leads to a tight coupling of the two components, resulting in samples and reconstructions of a comparable quality to some recently-proposed more complex architectures.
Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods
Venue: arXiv cs.DS 2017
Year: 2017

In this paper, we study matrix scaling and balancing, which are fundamental problems in scientific computing, with a long line of work on them that dates back to the 1960s. We provide algorithms for both these problems that, ignoring logarithmic factors involving the dimension of the input matrix and the size of its entries, both run in time $\widetilde{O}\left(m\log κ\log^2 (1/ε)\right)$ where $ε$ is the amount of error we are willing to tolerate. Here, $κ$ represents the ratio between the largest and the smallest entries of the optimal scalings. This implies that our algorithms run in nearly-linear time whenever $κ$ is quasi-polynomial, which includes, in particular, the case of strictly positive matrices. We complement our results by providing a separate algorithm that uses an interior-point method and runs in time $\widetilde{O}(m^{3/2} \log (1/ε))$. In order to establish these results, we develop a new second-order optimization framework that enables us to treat both problems in a unified and principled manner. This framework identifies a certain generalization of linear system solving that we can use to efficiently minimize a broad class of functions, which we call second-order robust. We then show that in the context of the specific functions capturing matrix scaling and balancing, we can leverage and generalize the work on Laplacian system solving to make the algorithms obtained via this framework very efficient.
A Constrained Sequence-to-Sequence Neural Model for Sentence Simplification
Venue: arXiv cs.CL 2017
Year: 2017

Sentence simplification reduces semantic complexity to benefit people with language impairments. Previous simplification studies on the sentence level and word level have achieved promising results but also meet great challenges. For sentence-level studies, sentences after simplification are fluent but sometimes are not really simplified. For word-level studies, words are simplified but also have potential grammar errors due to different usages of words before and after simplification. In this paper, we propose a two-step simplification framework by combining both the word-level and the sentence-level simplifications, making use of their corresponding advantages. Based on the two-step framework, we implement a novel constrained neural generation model to simplify sentences given simplified words. The final results on Wikipedia and Simple Wikipedia aligned datasets indicate that our method yields better performance than various baselines.
Stability of Service under Time-of-Use Pricing
Venue: arXiv cs.GT 2017
Year: 2017

We consider "time-of-use" pricing as a technique for matching supply and demand of temporal resources with the goal of maximizing social welfare. Relevant examples include energy, computing resources on a cloud computing platform, and charging stations for electric vehicles, among many others. A client/job in this setting has a window of time during which he needs service, and a particular value for obtaining it. We assume a stochastic model for demand, where each job materializes with some probability via an independent Bernoulli trial. Given a per-time-unit pricing of resources, any realized job will first try to get served by the cheapest available resource in its window and, failing that, will try to find service at the next cheapest available resource, and so on. Thus, the natural stochastic fluctuations in demand have the potential to lead to cascading overload events. Our main result shows that setting prices so as to optimally handle the {\em expected} demand works well: with high probability, when the actual demand is instantiated, the system is stable and the expected value of the jobs served is very close to that of the optimal offline algorithm.
Learning Where to Look: Data-Driven Viewpoint Set Selection for 3D Scenes
Venue: arXiv cs.CV 2017
Year: 2017

The use of rendered images, whether from completely synthetic datasets or from 3D reconstructions, is increasingly prevalent in vision tasks. However, little attention has been given to how the selection of viewpoints affects the performance of rendered training sets. In this paper, we propose a data-driven approach to view set selection. Given a set of example images, we extract statistics describing their contents and generate a set of views matching the distribution of those statistics. Motivated by semantic segmentation tasks, we model the spatial distribution of each semantic object category within an image view volume. We provide a search algorithm that generates a sampling of likely candidate views according to the example distribution, and a set selection algorithm that chooses a subset of the candidates that jointly cover the example distribution. Results of experiments with these algorithms on SUNCG indicate that they are indeed able to produce view distributions similar to an example set from NYUDv2 according to the earth mover's distance. Furthermore, the selected views improve performance on semantic segmentation compared to alternative view selection algorithms.
Towards Attack-Tolerant Networks: Concurrent Multipath Routing and the Butterfly Network
Venue: arXiv cs.CR 2017
Year: 2017

Targeted attacks against network infrastructure are notoriously difficult to guard against. In the case of communication networks, such attacks can leave users vulnerable to censorship and surveillance, even when cryptography is used. Much of the existing work on network fault-tolerance focuses on random faults and does not apply to adversarial faults (attacks). Centralized networks have single points of failure by definition, leading to a growing popularity in decentralized architectures and protocols for greater fault-tolerance. However, centralized network structure can arise even when protocols are decentralized. Despite their decentralized protocols, the Internet and World-Wide Web have been shown both theoretically and historically to be highly susceptible to attack, in part due to emergent structural centralization. When single points of failure exist, they are potentially vulnerable to non-technological (i.e., coercive) attacks, suggesting the importance of a structural approach to attack-tolerance. We show how the assumption of partial trust transitivity, while more realistic than the assumption underlying webs of trust, can be used to quantify the effective redundancy of a network as a function of trust transitivity. We also prove that the effective redundancy of the wrap-around butterfly topology increases exponentially with trust transitivity and describe a novel concurrent multipath routing algorithm for constructing paths to utilize that redundancy. When portions of network structure can be dictated our results can be used to create scalable, attack-tolerant infrastructures. More generally, our results provide a theoretical formalism for evaluating the effects of network structure on adversarial fault-tolerance.
Basic Formal Properties of A Relational Model of The Mathematical Theory of Evidence
Venue: arXiv cs.AI 2017
Year: 2017

The paper presents a novel view of the Dempster-Shafer belief function as a measure of diversity in relational data bases. It is demonstrated that under the interpretation The Dempster rule of evidence combination corresponds to the join operator of the relational database theory. This rough-set based interpretation is qualitative in nature and can represent a number of belief function operators. The interpretation has the property that Given a definition of the belief measure of objects in the interpretation domain we can perform operations in this domain and the measure of the resulting object is derivable from measures of component objects via belief operator. We demonstrated this property for Dempster rule of combination, marginalization, Shafer's conditioning, independent variables, Shenoy's notion of conditional independence of variables. The interpretation is based on rough sets (in connection with decision tables), but differs from previous interpretations of this type in that it counts the diversity rather than frequencies in a decision table.
LSH on the Hypercube Revisited
Venue: arXiv cs.CG 2017
Year: 2017

LSH (locality sensitive hashing) had emerged as a powerful technique in nearest-neighbor search in high dimensions [IM98, HIM12]. Given a point set $P$ in a metric space, and given parameters $r$ and $\varepsilon > 0$, the task is to preprocess the point set, such that given a query point $q$, one can quickly decide if $q$ is in distance at most $\leq r$ or $\geq (1+\varepsilon)r$ from the point set $P$. Once such a near-neighbor data-structure is available, one can reduce the general nearest-neighbor search to logarithmic number of queries in such structures [IM98, Har01, HIM12]. In this note, we revisit the most basic settings, where $P$ is a set of points in the binary hypercube $\{0,1\}^d$, under the $L_1$/Hamming metric, and present a short description of the LSH scheme in this case. We emphasize that there is no new contribution in this note, except (maybe) the presentation itself, which is inspired by the authors recent work [HM17].
Supervised Infinite Feature Selection
Venue: arXiv cs.LG 2017
Year: 2017

In this paper, we present a new feature selection method that is suitable for both unsupervised and supervised problems. We build upon the recently proposed Infinite Feature Selection (IFS) method where feature subsets of all sizes (including infinity) are considered. We extend IFS in two ways. First, we propose a supervised version of it. Second, we propose new ways of forming the feature adjacency matrix that perform better for unsupervised problems. We extensively evaluate our methods on many benchmark datasets, including large image-classification datasets (PASCAL VOC), and show that our methods outperform both the IFS and the widely used "minimum-redundancy maximum-relevancy (mRMR)" feature selection algorithm.
Pyramid Vector Quantization for Deep Learning
Venue: arXiv cs.LG 2017
Year: 2017

This paper explores the use of Pyramid Vector Quantization (PVQ) to reduce the computational cost for a variety of neural networks (NNs) while, at the same time, compressing the weights that describe them. This is based on the fact that the dot product between an N dimensional vector of real numbers and an N dimensional PVQ vector can be calculated with only additions and subtractions and one multiplication. This is advantageous since tensor products, commonly used in NNs, can be re-conduced to a dot product or a set of dot products. Finally, it is stressed that any NN architecture that is based on an operation that can be re-conduced to a dot product can benefit from the techniques described here.
A New Steganographic Technique Matching the Secret Message and Cover image Binary Value
Venue: arXiv cs.MM 2017
Year: 2017

Steganography involves hiding a secret message or image inside another cover image. Changes are made in the cover image without affecting visual quality of the image. In contrast to cryptography, Steganography provides complete secrecy of the communication. Security of very sensitive data can be enhanced by combining cryptography and steganography. A new technique that uses the concept of Steganography to obtain the position values from an image is suggested. This paper proposes a new method where no change is made to the cover image, only the pixel position LSB (Least Significant Bit) values that match with the secret message bit values are noted in a separate position file. At the sending end the position file along with the cover image is sent. At the receiving end the position file is opened only with a secret key. The bit positions are taken from the position file and the LSB values from the positions are combined to get ASCII values and then form characters of the secret message
Degrees of Freedom and Achievable Rate of Wide-Band Multi-cell Multiple Access Channels With No CSIT
Venue: arXiv cs.IT 2017
Year: 2017

This paper considers a $K$-cell multiple access channel with inter-symbol interference. The primary finding of this paper is that, without instantaneous channel state information at the transmitters (CSIT), the sum degrees-of-freedom (DoF) of the considered channel is $\frac{β-1}βK$ with $β\geq 2$ when the number of users per cell is sufficiently large, where $β$ is the ratio of the maximum channel-impulse-response (CIR) length of desired links to that of interfering links in each cell. Our finding implies that even without instantaneous CSIT, \textit{interference-free DoF per cell} is achievable as $β$ approaches infinity with a sufficiently large number of users per cell. This achievability is shown by a blind interference management method that exploits the relativity in delay spreads between desired and interfering links. In this method, all inter-cell-interference signals are aligned to the same direction by using a discrete-Fourier-transform-based precoding with cyclic prefix that only depends on the number of CIR taps. Using this method, we also characterize the achievable sum rate of the considered channel, in a closed-form expression.
Robust Connectivity with Multiple Nonisotropic Antennas for Vehicular Communications
Venue: arXiv cs.IT 2017
Year: 2017

For critical services, such as traffic safety and traffic efficiency, it is advisable to design systems with robustness as the main criteria, possibly at the price of reduced peak performance and efficiency. Ensuring robust communications in case of embedded or hidden antennas is a challenging task due to nonisotropic radiation patterns of these antennas. The challenges due to the nonisotropic radiation patterns can be overcome with the use of multiple antennas. In this paper, we describe a simple, low-cost method for combining the output of multiple nonisotropic antennas to guarantee robustness, i.e., support reliable communications in worst-case scenarios. The combining method is designed to minimize the burst error probability, i.e., the probability of consecutive decoding errors of status messages arriving periodically at a receiver from an arbitrary angle of arrival. The proposed method does not require the knowledge of instantaneous signal-to-noise ratios or the complex-valued channel gains at the antenna outputs. The proposed method is applied to measured and theoretical antenna radiation patterns, and it is shown that the method supports robust communications from an arbitrary angle of arrival.
A Synchronization Algorithm Based on Moving Average for Robust Audio Watermarking Scheme
Venue: arXiv cs.MM 2017
Year: 2017

A synchronization code scheme based on moving average is proposed for robust audio watermarking in the paper. Two proper positive integers are chosen to compute the moving average sequence by sliding one sample every time. The synchronization bits are embedded at crosses of the two moving average sequences with the quantization index modulation. The experimental results show that the proposed watermarking scheme maintains high audio quality and is robust to common attacks such as additive white Gaussian noise, re-sampling, low-pass filtering, random cropping, MP3 compression, jitter attack and time scale modification. Simultaneously, the algorithm has high search efficiency and low false alarm rate.