OpenRaiser/Intern-Atlas huggingface dataset:
Generating images with recurrent adversarial networks
Venue: arXiv cs.LG 2016
Year: 2016

Gatys et al. (2015) showed that optimizing pixels to match features in a convolutional network with respect reference image features is a way to render images of high visual quality. We show that unrolling this gradient-based optimization yields a recurrent computation that creates images by incrementally adding onto a visual "canvas". We propose a recurrent generative model inspired by this view, and show that it can be trained using adversarial training to generate very good image samples. We also propose a way to quantitatively compare adversarial networks by having the generators and discriminators of these networks compete against each other.
Approximation and Hardness for Token Swapping
Venue: arXiv cs.CC 2016
Year: 2016

Given a graph $G=(V,E)$ with $V=\{1,\ldots,n\}$, we place on every vertex a token $T_1,\ldots,T_n$. A swap is an exchange of tokens on adjacent vertices. We consider the algorithmic question of finding a shortest sequence of swaps such that token $T_i$ is on vertex $i$. We are able to achieve essentially matching upper and lower bounds, for exact algorithms and approximation algorithms. For exact algorithms, we rule out any $2^{o(n)}$ algorithm under the ETH. This is matched with a simple $2^{O(n\log n)}$ algorithm based on a breadth-first search in an auxiliary graph. We show one general $4$-approximation and show APX-hardness. Thus, there is a small constant $δ>1$ such that every polynomial time approximation algorithm has approximation factor at least $δ$. Our results also hold for a generalized version, where tokens and vertices are colored. In this generalized version each token must go to a vertex with the same color.
An Approach for Noise Removal on Depth Images
Venue: arXiv cs.CV 2016
Year: 2016

Image based rendering is a fundamental problem in computer vision and graphics. Modern techniques often rely on depth image for the 3D construction. However for most of the existing depth cameras, the large and unpredictable noises can be problematic, which can cause noticeable artifacts in the rendered results. In this paper, we proposed an efficacious method for depth image noise removal that can be applied for most RGBD systems. The proposed solution will benefit many subsequent vision problems such as 3D reconstruction, novel view rendering, object recognition. Our experimental results demonstrate the efficacy and accuracy.
Development and Experimentation of a Software Tool for Identifying High Risk Spreadsheets for Auditing
Venue: arXiv cs.SE 2016
Year: 2016

Heavy use of spreadsheets by organisations bears many potential risks such as errors, ambiguity, data loss, duplication, and fraud. In this paper these risks are briefly outlined along with their available mitigation methods such as: documentation, centralisation, auditing and user training. However, because of the large quantities of spreadsheets used in organisations, applying these methods on all spreadsheets is impossible. This fact is considered as a deficiency in these methods, a gap which is addressed in this paper. In this paper a new software tool for managing spreadsheets and identifying the risk levels they include is proposed, developed and tested. As an add-in for Microsoft Excel application, "Risk Calculator" can automatically collect and record spreadsheet properties in an inventory database and assign risk scores based on their importance, use and complexity. Consequently, auditing processes can be targeted to high risk spreadsheets. Such a method saves time, effort, and money.
Relative Error Embeddings for the Gaussian Kernel Distance
Venue: arXiv cs.LG 2016
Year: 2016

A reproducing kernel can define an embedding of a data point into an infinite dimensional reproducing kernel Hilbert space (RKHS). The norm in this space describes a distance, which we call the kernel distance. The random Fourier features (of Rahimi and Recht) describe an oblivious approximate mapping into finite dimensional Euclidean space that behaves similar to the RKHS. We show in this paper that for the Gaussian kernel the Euclidean norm between these mapped to features has $(1+ε)$-relative error with respect to the kernel distance. When there are $n$ data points, we show that $O((1/ε^2) \log(n))$ dimensions of the approximate feature space are sufficient and necessary. Without a bound on $n$, but when the original points lie in $\mathbb{R}^d$ and have diameter bounded by $\mathcal{M}$, then we show that $O((d/ε^2) \log(\mathcal{M}))$ dimensions are sufficient, and that this many are required, up to $\log(1/ε)$ factors.
DOA Parameter Estimation with 1-bit Quantization - Bounds, Methods and the Exponential Replacement
Venue: arXiv cs.IT 2016
Year: 2016

While 1-bit analog-to-digital conversion (ADC) allows to significantly reduce the analog complexity of wireless receive systems, using the exact likelihood function of the hard-limiting system model in order to obtain efficient algorithms in the digital domain can make 1-bit signal processing challenging. If the signal model before the quantizer consists of correlated Gaussian random variables, the tail probability for a multivariate Gaussian distribution with N dimensions (general orthant probability) is required in order to formulate the likelihood function of the quantizer output. As a closed-form expression for the general orthant probability is an open mathematical problem, formulation of efficient processing methods for correlated and quantized data and an analytical performance assessment have, despite their high practical relevance, only found limited attention in the literature on quantized estimation theory. Here we review the approach of replacing the original system model by an equivalent distribution within the exponential family. For 1-bit signal processing, this allows to circumvent calculation of the general orthant probability and gives access to a conservative approximation of the receive likelihood. For the application of blind direction-of-arrival (DOA) parameter estimation with an array of K sensors, each performing 1-bit quantization, we demonstrate how the exponential replacement enables to formulate a pessimistic version of the Cramér-Rao lower bound (CRLB) and to derive an asymptotically achieving conservative maximum-likelihood estimator (CMLE). The 1-bit DOA performance analysis based on the pessimistic CRLB points out that a low-complexity radio front-end design with 1-bit ADC is in particular suitable for blind wireless DOA estimation with a large number of array elements operating in the medium SNR regime.
Backhaul Traffic Balancing and Dynamic Content-Centric Clustering for the Downlink of Fog Radio Access Network
Venue: arXiv cs.IT 2016
Year: 2016

Recently, an evolution of the Cloud Radio Access Network (C-RAN) has been proposed, named as Fog Radio Access Network (F-RAN). Compared to C-RAN, the Radio Units (RUs) in F-CAN are equipped with local caches, which can store some frequently requested files. In the downlink, users requesting the same file form a multicast group, and are cooperatively served by a cluster of RUs. The requested file is either available locally in the cache of this cluster or fetched from the Central Processor (CP) via backhauls. Thus caching some frequently requested files can greatly reduce the burden on backhaul links. Whether a specific RU should be involved in a cluster to serve a multicast group depends on its backhaul capacity, requested files, cached files and the channel. Therefore it is subject to optimization. In this paper we investigate the joint design of multicast beamforming, dynamic clustering and backhaul traffic balancing. Beamforming and clustering are jointly optimized in order to minimize the power consumed, while QoS of each user is to be met and the traffic on each backhaul link is balanced according to its capacity.
On the Power of Attribute-based Communication
Venue: arXiv cs.LO 2016
Year: 2016

In open systems, i.e. systems operating in an environment that they cannot control and with components that may join or leave, behaviors can arise as side effects of intensive components interaction. Finding ways to understand and design these systems and, most of all, to model the interactions of their components, is a difficult but important endeavor. To tackle these issues, we present AbC, a calculus for attribute-based communication. An AbC system consists of a set of parallel agents each of which is equipped with a set of attributes. Communication takes place in an implicit multicast fashion, and interactions among agents are dynamically established by taking into account "connections" as determined by predicates over the attributes of agents. First, the syntax and the semantics of the calculus are presented, then expressiveness and effectiveness of AbC are demonstrated both in terms of modeling scenarios featuring collaboration, reconfiguration, and adaptation and of the possibility of encoding channel-based interactions and other interaction patterns. Behavioral equivalences for AbC are introduced for establishing formal relationships between different descriptions of the same system.
Memory-Centred Cognitive Architectures for Robots Interacting Socially with Humans
Venue: arXiv cs.RO 2016
Year: 2016

The Memory-Centred Cognition perspective places an active association substrate at the heart of cognition, rather than as a passive adjunct. Consequently, it places prediction and priming on the basis of prior experience to be inherent and fundamental aspects of processing. Social interaction is taken here to minimally require contingent and co-adaptive behaviours from the interacting parties. In this contribution, I seek to show how the memory-centred cognition approach to cognitive architectures can provide an means of addressing these functions. A number of example implementations are briefly reviewed, particularly focusing on multi-modal alignment as a function of experience-based priming. While there is further refinement required to the theory, and implementations based thereon, this approach provides an interesting alternative perspective on the foundations of cognitive architectures to support robots engage in social interactions with humans.
Corpus analysis without prior linguistic knowledge - unsupervised mining of phrases and subphrase structure
Venue: arXiv cs.CL 2016
Year: 2016

When looking at the structure of natural language, "phrases" and "words" are central notions. We consider the problem of identifying such "meaningful subparts" of language of any length and underlying composition principles in a completely corpus-based and language-independent way without using any kind of prior linguistic knowledge. Unsupervised methods for identifying "phrases", mining subphrase structure and finding words in a fully automated way are described. This can be considered as a step towards automatically computing a "general dictionary and grammar of the corpus". We hope that in the long run variants of our approach turn out to be useful for other kind of sequence data as well, such as, e.g., speech, genom sequences, or music annotation. Even if we are not primarily interested in immediate applications, results obtained for a variety of languages show that our methods are interesting for many practical tasks in text mining, terminology extraction and lexicography, search engine technology, and related fields.
A General Modifier-based Framework for Inconsistency-Tolerant Query Answering
Venue: arXiv cs.AI 2016
Year: 2016

We propose a general framework for inconsistency-tolerant query answering within existential rule setting. This framework unifies the main semantics proposed by the state of art and introduces new ones based on cardinality and majority principles. It relies on two key notions: modifiers and inference strategies. An inconsistency-tolerant semantics is seen as a composite modifier plus an inference strategy. We compare the obtained semantics from a productivity point of view.
An Iterative Linearised Solution to the Sinusoidal Parameter Estimation Problem
Venue: arXiv cs.SD 2016
Year: 2016

Signal processing applications use sinusoidal modelling for speech synthesis, speech coding, and audio coding. Estimation of the model parameters involves non-linear optimisation methods, which can be very costly for real-time applications. We propose a low-complexity iterative method that starts from initial frequency estimates and converges rapidly. We show that for N sinusoids in a frame of length L, the proposed method has a complexity of O(LN), which is significantly less than the matching pursuits method. Furthermore, the proposed method is shown to be more accurate than the matching pursuits and time-frequency reassignment methods in our experiments.
On the Complexity of Weighted Greedy Matchings
Venue: arXiv cs.DM 2016
Year: 2016

Motivated by the fact that in several cases a matching in a graph is stable if and only if it is produced by a greedy algorithm, we study the problem of computing a maximum weight greedy matching on weighted graphs, termed GreedyMatching. In wide contrast to the maximum weight matching problem, for which many efficient algorithms are known, we prove that GreedyMatching is strongly NP-hard and APX-complete, and thus it does not admit a PTAS unless P=NP, even on graphs with maximum degree at most 3 and with at most three different integer edge weights. Furthermore we prove that GreedyMatching is strongly NP-hard if the input graph is in addition bipartite. Moreover we consider two natural parameters of the problem, for which we establish a sharp threshold behavior between NP-hardness and tractability. On the positive side, we present a randomized approximation algorithm (RGMA) for GreedyMatching on a special class of weighted graphs, called bush graphs. We highlight an unexpected connection between RGMA and the approximation of maximum cardinality matching in unweighted graphs via randomized greedy algorithms. We show that, if the approximation ratio of RGMA is $ρ$, then for every $ε>0$ the randomized MRG algorithm of [Aronson et al., Rand. Struct. Alg. 1995] gives a $(ρ-ε)$-approximation for the maximum cardinality matching. We conjecture that a tight bound for $ρ$ is $\frac{2}{3}$; we prove our conjecture true for two subclasses of bush graphs. Proving a tight bound for the approximation ratio of MRG on unweighted graphs (and thus also proving a tight value for $ρ$) is a long-standing open problem [Poloczek and Szegedy; FOCS 2012]. This unexpected relation of our RGMA algorithm with the MRG algorithm may provide new insights for solving this problem.
The Interaction of Memory and Attention in Novel Word Generalization: A Computational Investigation
Venue: arXiv cs.CL 2016
Year: 2016

People exhibit a tendency to generalize a novel noun to the basic-level in a hierarchical taxonomy -- a cognitively salient category such as "dog" -- with the degree of generalization depending on the number and type of exemplars. Recently, a change in the presentation timing of exemplars has also been shown to have an effect, surprisingly reversing the prior observed pattern of basic-level generalization. We explore the precise mechanisms that could lead to such behavior by extending a computational model of word learning and word generalization to integrate cognitive processes of memory and attention. Our results show that the interaction of forgetting and attention to novelty, as well as sensitivity to both type and token frequencies of exemplars, enables the model to replicate the empirical results from different presentation timings. Our results reinforce the need to incorporate general cognitive processes within word learning models to better understand the range of observed behaviors in vocabulary acquisition.
Achieving both High Energy Efficiency and High Performance in On-Chip Communication using Hierarchical Rings with Deflection Routing
Venue: arXiv cs.DC 2016
Year: 2016

Hierarchical ring networks, which hierarchically connect multiple levels of rings, have been proposed in the past to improve the scalability of ring interconnects, but past hierarchical ring designs sacrifice some of the key benefits of rings by introducing more complex in-ring buffering and buffered flow control. Our goal in this paper is to design a new hierarchical ring interconnect that can maintain most of the simplicity of traditional ring designs (no in-ring buffering or buffered flow control) while achieving high scalability as more complex buffered hierarchical ring designs. Our design, called HiRD (Hierarchical Rings with Deflection), includes features that allow us to mostly maintain the simplicity of traditional simple ring topologies while providing higher energy efficiency and scalability. First, HiRD does not have any buffering or buffered flow control within individual rings, and requires only a small amount of buffering between the ring hierarchy levels. When inter-ring buffers are full, our design simply deflects flits so that they circle the ring and try again, which eliminates the need for in-ring buffering. Second, we introduce two simple mechanisms that provides an end-to-end delivery guarantee within the entire network without impacting the critical path or latency of the vast majority of network traffic. HiRD attains equal or better performance at better energy efficiency than multiple versions of both a previous hierarchical ring design and a traditional single ring design. We also analyze our design's characteristics and injection and delivery guarantees. We conclude that HiRD can be a compelling design point that allows higher energy efficiency and scalability while retaining the simplicity and appeal of conventional ring-based designs.
Hardware Architecture of Complex K-best MIMO Decoder
Venue: arXiv cs.IT 2016
Year: 2016

This paper presents a hardware architecture of complex K-best Multiple Input Multiple Output (MIMO) decoder reducing the complexity of Maximum Likelihood (ML) detector. We develop a novel low-power VLSI design of complex K-best decoder for 8x8 MIMO and 64 QAM modulation scheme. Use of Schnorr-Euchner (SE) enumeration and a new parameter, Rlimit in the design reduce the complexity of calculating K-best nodes to a certain level with increased performance. The total word length of only 16 bits has been adopted for the hardware design limiting the bit error rate (BER) degradation to 0.3 dB with list size, K and Rlimit equal to 4. The proposed VLSI architecture is modeled in Verilog HDL using Xilinx and synthesized using Synopsys Design Vision in 45 nm CMOS technology. According to the synthesize result, it achieves 1090.8 Mbps throughput with power consumption of 782 mW and latency of 0.044 us. The maximum frequency the design proposed is 181.8 MHz.
PSPACE-Complete Two-Color Placement Games
Venue: arXiv cs.CC 2016
Year: 2016

We show that three placement games, Col, NoGo, and Fjords, are PSPACE-complete on planar graphs. The hardness of Col and Fjords is shown via a reduction from Bounded 2-Player Constraint Logic and NoGo is shown to be hard directly from Col.
GBLA -- Gröbner Basis Linear Algebra Package
Venue: arXiv cs.SC 2016
Year: 2016

This is a system paper about a new GPLv2 open source C library GBLA implementing and improving the idea of Faugère and Lachartre (GB reduction). We further exploit underlying structures in matrices generated during Gröbner basis computations in algorithms like F4 or F5 taking advantage of block patterns by using a special data structure called multilines. Moreover, we discuss a new order of operations for the reduction process. In various different experimental results we show that GBLA performs better than GB reduction or Magma in sequential computations (up to 40% faster) and scales much better than GB reduction for a higher number of cores: On 32 cores we reach a scaling of up to 26. GBLA is up to 7 times faster than GB reduction. Further, we compare different parallel schedulers GBLA can be used with. We also developed a new advanced storage format that exploits the fact that our matrices are coming from Gröbner basis computations, shrinking storage by a factor of up to 4. A huge database of our matrices is freely available with GBLA.
Large age-gap face verification by feature injection in deep networks
Venue: arXiv cs.CV 2016
Year: 2016

This paper introduces a new method for face verification across large age gaps and also a dataset containing variations of age in the wild, the Large Age-Gap (LAG) dataset, with images ranging from child/young to adult/old. The proposed method exploits a deep convolutional neural network (DCNN) pre-trained for the face recognition task on a large dataset and then fine-tuned for the large age-gap face verification task. Finetuning is performed in a Siamese architecture using a contrastive loss function. A feature injection layer is introduced to boost verification accuracy, showing the ability of the DCNN to learn a similarity metric leveraging external features. Experimental results on the LAG dataset show that our method is able to outperform the face verification solutions in the state of the art considered.
Node-By-Node Greedy Deep Learning for Interpretable Features
Venue: arXiv cs.LG 2016
Year: 2016

Multilayer networks have seen a resurgence under the umbrella of deep learning. Current deep learning algorithms train the layers of the network sequentially, improving algorithmic performance as well as providing some regularization. We present a new training algorithm for deep networks which trains \emph{each node in the network} sequentially. Our algorithm is orders of magnitude faster, creates more interpretable internal representations at the node level, while not sacrificing on the ultimate out-of-sample performance.
Rules of Acquisition for Mementos and Their Content
Venue: arXiv cs.DL 2016
Year: 2016

Text extraction from web pages has many applications, including web crawling optimization and document clustering. Though much has been written about the acquisition of content from live web pages, content acquisition of archived web pages, known as mementos, remains a relatively new enterprise. In the course of conducting a study with almost 700,000 web pages, we encountered issues acquiring mementos and extracting text from them. The acquisition of memento content via HTTP is expected to be a relatively painless exercise, but we have found cases to the contrary. We also find that the parsing of HTML, already known to be problematic, can be more complex when one attempts to extract the text of mementos across many web archives, due to issues involving different memento presentation behaviors, as well as the age of the HTML in their mementos. For the benefit of others acquiring mementos across many web archives, we document those experiences here.
A Reduction System for Optimal 1-Planar Graphs
Venue: arXiv cs.CG 2016
Year: 2016

There is a graph reduction system so that every optimal 1-planar graph can be reduced to an irreducible extended wheel graph, provided the reductions are applied such that the given graph class is preserved. A graph is optimal 1-planar if it can be drawn in the plane with at most one crossing per edge and is optimal if it has the maximum of 4n-8 edges. We show that the reduction system is context-sensitive so that the preservation of the graph class can be granted by local conditions which can be tested in constant time. Every optimal 1-planar graph G can be reduced to every extended wheel graph whose size is in a range from the (second) smallest one to some upper bound that depends on G. There is a reduction to the smallest extended wheel graph if G is not 5-connected, but not conversely. The reduction system has side effects and is non-deterministic and non-confluent. Nevertheless, reductions can be computed in linear time.