OpenRaiser/Intern-Atlas huggingface dataset:
Hierarchical Question-Image Co-Attention for Visual Question Answering
Venue: arXiv cs.CV 2017
Year: 2017

A number of recent works have proposed attention models for Visual Question Answering (VQA) that generate spatial maps highlighting image regions relevant to answering the question. In this paper, we argue that in addition to modeling "where to look" or visual attention, it is equally important to model "what words to listen to" or question attention. We present a novel co-attention model for VQA that jointly reasons about image and question attention. In addition, our model reasons about the question (and consequently the image via the co-attention mechanism) in a hierarchical fashion via a novel 1-dimensional convolution neural networks (CNN). Our model improves the state-of-the-art on the VQA dataset from 60.3% to 60.5%, and from 61.6% to 63.3% on the COCO-QA dataset. By using ResNet, the performance is further improved to 62.1% for VQA and 65.4% for COCO-QA.
Source-LDA: Enhancing probabilistic topic models using prior knowledge sources
Venue: arXiv cs.CL 2017
Year: 2017

A popular approach to topic modeling involves extracting co-occurring n-grams of a corpus into semantic themes. The set of n-grams in a theme represents an underlying topic, but most topic modeling approaches are not able to label these sets of words with a single n-gram. Such labels are useful for topic identification in summarization systems. This paper introduces a novel approach to labeling a group of n-grams comprising an individual topic. The approach taken is to complement the existing topic distributions over words with a known distribution based on a predefined set of topics. This is done by integrating existing labeled knowledge sources representing known potential topics into the probabilistic topic model. These knowledge sources are translated into a distribution and used to set the hyperparameters of the Dirichlet generated distribution over words. In the inference these modified distributions guide the convergence of the latent topics to conform with the complementary distributions. This approach ensures that the topic inference process is consistent with existing knowledge. The label assignment from the complementary knowledge sources are then transferred to the latent topics of the corpus. The results show both accurate label assignment to topics as well as improved topic generation than those obtained using various labeling approaches based off Latent Dirichlet allocation (LDA).
A Spiking Network that Learns to Extract Spike Signatures from Speech Signals
Venue: arXiv cs.NE 2017
Year: 2017

Spiking neural networks (SNNs) with adaptive synapses reflect core properties of biological neural networks. Speech recognition, as an application involving audio coding and dynamic learning, provides a good test problem to study SNN functionality. We present a simple, novel, and efficient nonrecurrent SNN that learns to convert a speech signal into a spike train signature. The signature is distinguishable from signatures for other speech signals representing different words, thereby enabling digit recognition and discrimination in devices that use only spiking neurons. The method uses a small, nonrecurrent SNN consisting of Izhikevich neurons equipped with spike timing dependent plasticity (STDP) and biologically realistic synapses. This approach introduces an efficient and fast network without error-feedback training, although it does require supervised training. The new simulation results produce discriminative spike train patterns for spoken digits in which highly correlated spike trains belong to the same category and low correlated patterns belong to different categories. The proposed SNN is evaluated using a spoken digit recognition task where a subset of the Aurora speech dataset is used. The experimental results show that the network performs well in terms of accuracy rate and complexity.
The Complexity of Computing all Subfields of an Algebraic Number Field
Venue: arXiv cs.SC 2017
Year: 2017

For a finite separable field extension K/k, all subfields can be obtained by intersecting so-called principal subfields of K/k. In this work we present a way to quickly compute these intersections. If the number of subfields is high, then this leads to faster run times and an improved complexity.
On Valid Optimal Assignment Kernels and Applications to Graph Classification
Venue: arXiv cs.LG 2017
Year: 2017

The success of kernel methods has initiated the design of novel positive semidefinite functions, in particular for structured data. A leading design paradigm for this is the convolution kernel, which decomposes structured objects into their parts and sums over all pairs of parts. Assignment kernels, in contrast, are obtained from an optimal bijection between parts, which can provide a more valid notion of similarity. In general however, optimal assignments yield indefinite functions, which complicates their use in kernel methods. We characterize a class of base kernels used to compare parts that guarantees positive semidefinite optimal assignment kernels. These base kernels give rise to hierarchies from which the optimal assignment kernels are computed in linear time by histogram intersection. We apply these results by developing the Weisfeiler-Lehman optimal assignment kernel for graphs. It provides high classification accuracy on widely-used benchmark data sets improving over the original Weisfeiler-Lehman kernel.
Generalizing the Convolution Operator to extend CNNs to Irregular Domains
Venue: arXiv cs.LG 2017
Year: 2017

Convolutional Neural Networks (CNNs) have become the state-of-the-art in supervised learning vision tasks. Their convolutional filters are of paramount importance for they allow to learn patterns while disregarding their locations in input images. When facing highly irregular domains, generalized convolutional operators based on an underlying graph structure have been proposed. However, these operators do not exactly match standard ones on grid graphs, and introduce unwanted additional invariance (e.g. with regards to rotations). We propose a novel approach to generalize CNNs to irregular domains using weight sharing and graph-based operators. Using experiments, we show that these models resemble CNNs on regular domains and offer better performance than multilayer perceptrons on distorded ones.
Predicting with Distributions
Venue: arXiv cs.DS 2017
Year: 2017

We consider a new learning model in which a joint distribution over vector pairs $(x,y)$ is determined by an unknown function $c(x)$ that maps input vectors $x$ not to individual outputs, but to entire {\em distributions\/} over output vectors $y$. Our main results take the form of rather general reductions from our model to algorithms for PAC learning the function class and the distribution class separately, and show that virtually every such combination yields an efficient algorithm in our model. Our methods include a randomized reduction to classification noise and an application of Le Cam's method to obtain robust learning algorithms.
HopsFS: Scaling Hierarchical File System Metadata Using NewSQL Databases
Venue: arXiv cs.DC 2017
Year: 2017

Recent improvements in both the performance and scalability of shared-nothing, transactional, in-memory NewSQL databases have reopened the research question of whether distributed metadata for hierarchical file systems can be managed using commodity databases. In this paper, we introduce HopsFS, a next generation distribution of the Hadoop Distributed File System (HDFS) that replaces HDFS' single node in-memory metadata service, with a distributed metadata service built on a NewSQL database. By removing the metadata bottleneck, HopsFS enables an order of magnitude larger and higher throughput clusters compared to HDFS. Metadata capacity has been increased to at least 37 times HDFS' capacity, and in experiments based on a workload trace from Spotify, we show that HopsFS supports 16 to 37 times the throughput of Apache HDFS. HopsFS also has lower latency for many concurrent clients, and no downtime during failover. Finally, as metadata is now stored in a commodity database, it can be safely extended and easily exported to external systems for online analysis and free-text search.
The Circle Game: Scalable Private Membership Test Using Trusted Hardware
Venue: arXiv cs.CR 2017
Year: 2017

Malware checking is changing from being a local service to a cloud-assisted one where users' devices query a cloud server, which hosts a dictionary of malware signatures, to check if particular applications are potentially malware. Whilst such an architecture gains all the benefits of cloud-based services, it opens up a major privacy concern since the cloud service can infer personal traits of the users based on the lists of applications queried by their devices. Private membership test (PMT) schemes can remove this privacy concern. However, known PMT schemes do not scale well to a large number of simultaneous users and high query arrival rates. We propose a simple PMT approach using a carousel: circling the entire dictionary through trusted hardware on the cloud server. Users communicate with the trusted hardware via secure channels. We show how the carousel approach, using different data structures to represent the dictionary, can be realized on two different commercial hardware security architectures (ARM TrustZone and Intel SGX). We highlight subtle aspects of securely implementing seemingly simple PMT schemes on these architectures. Through extensive experimental analysis, we show that for the malware checking scenario our carousel approach surprisingly outperforms Path ORAM on the same hardware by supporting a much higher query arrival rate while guaranteeing acceptable response latency for individual queries.
A Minimum Spanning Tree Representation of Anime Similarities
Venue: arXiv cs.IR 2017
Year: 2017

In this work, a new way to represent Japanese animation (anime) is presented. We applied a minimum spanning tree to show the relation between anime. The distance between anime is calculated through three similarity measurements, namely crew, score histogram, and topic similarities. Finally, the centralities are also computed to reveal the most significance anime. The result shows that the minimum spanning tree can be used to determine the similarity anime. Furthermore, by using centralities calculation, we found some anime that are significant to others.
Cooperative Data Offload in Opportunistic Networks: From Mobile Devices to Infrastructure
Venue: arXiv cs.NI 2017
Year: 2017

Opportunistic mobile networks consisting of intermittently connected mobile devices have been exploited for various applications, such as computational offloading and mitigating cellular traffic load. In contrast to existing work, in this paper, we focus on cooperatively offloading data among mobile devices to maximally improve the probability of data delivery from a mobile device to intermittently connected infrastructure within a given time constraint, which is referred to as the \textit{cooperative offloading} problem. Unfortunately, the estimation of data delivery probability over an opportunistic path is difficult and cooperative offloading is NP-hard. To this end, we first propose a probabilistic framework that provides the estimation of such probability. Based on the proposed probabilistic framework, we design a heuristic algorithm to solve cooperative offloading at a low computation cost. Due to the lack of global information, a distributed algorithm is further proposed. The performance of the proposed approaches is evaluated based on both synthetic networks and real traces. Experimental results show that the probabilistic framework can accurately estimate the data delivery probability, cooperative offloading greatly improves the delivery probability, the heuristic algorithm approximates the optimum, and the performance of both the heuristic algorithm and distributed algorithm outperforms other approaches.
Spatial and Social Paradigms for Interference and Coverage Analysis in Underlay D2D Network
Venue: arXiv cs.IT 2017
Year: 2017

The homogeneous Poisson point process (PPP) is widely used to model spatial distribution of base stations and mobile terminals. The same process can be used to model underlay device-to-device (D2D) network, however, neglecting homophilic relation for D2D pairing presents underestimated system insights. In this paper, we model both spatial and social distributions of interfering D2D nodes as proximity based independently marked homogeneous Poisson point process. The proximity considers physical distance between D2D nodes whereas social relationship is modeled as Zipf based marks. We apply these two paradigms to analyze the effect of interference on coverage probability of distance-proportional power-controlled cellular user. Effectively, we apply two type of functional mappings (physical distance, social marks) to Laplace functional of PPP. The resulting coverage probability has no closed-form expression, however for a subset of social marks, the mark summation converges to digamma and polygamma functions. This subset constitutes the upper and lower bounds on coverage probability. We present numerical evaluation of these bounds on coverage probability by varying number of different parameters. The results show that by imparting simple power control on cellular user, ultra-dense underlay D2D network can be realized without compromising the coverage probability of cellular user.
Critical Echo State Networks that Anticipate Input using Morphable Transfer Functions
Venue: arXiv cs.NE 2017
Year: 2017

The paper investigates a new type of truly critical echo state networks where individual transfer functions for every neuron can be modified to anticipate the expected next input. Deviations from expected input are only forgotten slowly in power law fashion. The paper outlines the theory, numerically analyzes a one neuron model network and finally discusses technical and also biological implications of this type of approach.
Application-Driven Near-Data Processing for Similarity Search
Venue: arXiv cs.DC 2017
Year: 2017

Similarity search is a key to a variety of applications including content-based search for images and video, recommendation systems, data deduplication, natural language processing, computer vision, databases, computational biology, and computer graphics. At its core, similarity search manifests as k-nearest neighbors (kNN), a computationally simple primitive consisting of highly parallel distance calculations and a global top-k sort. However, kNN is poorly supported by today's architectures because of its high memory bandwidth requirements. This paper proposes an application-driven near-data processing accelerator for similarity search: the Similarity Search Associative Memory (SSAM). By instantiating compute units close to memory, SSAM benefits from the higher memory bandwidth and density exposed by emerging memory technologies. We evaluate the SSAM design down to layout on top of the Micron hybrid memory cube (HMC), and show that SSAM can achieve up to two orders of magnitude area-normalized throughput and energy efficiency improvement over multicore CPUs; we also show SSAM is faster and more energy efficient than competing GPUs and FPGAs. Finally, we show that SSAM is also useful for other data intensive tasks like kNN index construction, and can be generalized to semantically function as a high capacity content addressable memory.
The Chasm at Depth Four, and Tensor Rank : Old results, new insights
Venue: arXiv cs.CC 2017
Year: 2017

Agrawal and Vinay [AV08] showed how any polynomial size arithmetic circuit can be thought of as a depth four arithmetic circuit of subexponential size. The resulting circuit size in this simulation was more carefully analyzed by Korian [Koiran] and subsequently by Tavenas [Tav13]. We provide a simple proof of this chain of results. We then abstract the main ingredient to apply it to formulas and constant depth circuits, and show more structured depth reductions for them. In an apriori surprising result, Raz [Raz10] showed that for any $n$ and $d$, such that $ ω(1) \leq d \leq O\left(\frac{\log n}{\log\log n}\right)$, constructing explicit tensors $T:[n]^d \rightarrow F$ of high enough rank would imply superpolynomial lower bounds for arithmetic formulas over the field $F$. Using the additional structure we obtain from our proof of the depth reduction for arithmetic formulas, we give a new and arguably simpler proof of this connection. We also extend this result for homogeneous formulas to show that, in fact, the connection holds for any $d$ such that $ω(1) \leq d \leq n^{o(1)}$.
Richardson-Lucy Deblurring for Moving Light Field Cameras
Venue: arXiv cs.CV 2017
Year: 2017

We generalize Richardson-Lucy (RL) deblurring to 4-D light fields by replacing the convolution steps with light field rendering of motion blur. The method deals correctly with blur caused by 6-degree-of-freedom camera motion in complex 3-D scenes, without performing depth estimation. We introduce a novel regularization term that maintains parallax information in the light field while reducing noise and ringing. We demonstrate the method operating effectively on rendered scenes and scenes captured using an off-the-shelf light field camera. An industrial robot arm provides repeatable and known trajectories, allowing us to establish quantitative performance in complex 3-D scenes. Qualitative and quantitative results confirm the effectiveness of the method, including commonly occurring cases for which previously published methods fail. We include mathematical proof that the algorithm converges to the maximum-likelihood estimate of the unblurred scene under Poisson noise. We expect extension to blind methods to be possible following the generalization of 2-D Richardson-Lucy to blind deconvolution.
Survey of Distributed Decision
Venue: arXiv cs.DC 2017
Year: 2017

We survey the recent distributed computing literature on checking whether a given distributed system configuration satisfies a given boolean predicate, i.e., whether the configuration is legal or illegal w.r.t. that predicate. We consider classical distributed computing environments, including mostly synchronous fault-free network computing (LOCAL and CONGEST models), but also asynchronous crash-prone shared-memory computing (WAIT-FREE model), and mobile computing (FSYNC model).
A linear time algorithm for a variant of the max cut problem in series parallel graphs
Venue: arXiv cs.DS 2017
Year: 2017

Given a graph $G=(V, E)$, a connected sides cut $(U, V\backslash U)$ or $δ(U)$ is the set of edges of E linking all vertices of U to all vertices of $V\backslash U$ such that the induced subgraphs $G[U]$ and $G[V\backslash U]$ are connected. Given a positive weight function $w$ defined on $E$, the maximum connected sides cut problem (MAX CS CUT) is to find a connected sides cut $Ω$ such that $w(Ω)$ is maximum. MAX CS CUT is NP-hard. In this paper, we give a linear time algorithm to solve MAX CS CUT for series parallel graphs. We deduce a linear time algorithm for the minimum cut problem in the same class of graphs without computing the maximum flow.
Image Edge Detection based on Swarm Intelligence using Memristive Networks
Venue: arXiv cs.ET 2017
Year: 2017

Recent advancements in the development of memristive devices has opened new opportunities for hardware implementation of non-Boolean computing. To this end, the suitability of memristive devices for swarm intelligence algorithms has enabled researchers to solve a maze in hardware. In this paper, we utilize swarm intelligence of memristive networks to perform image edge detection. First, we propose a hardware-friendly algorithm for image edge detection based on ant colony. Second, we implement the image edge detection algorithm using memristive networks. Furthermore, we explain the impact of various parameters of the memristors on the efficacy of the implementation. Our results show 28% improvement in the energy compared to a low power CMOS hardware implementation based on stochastic circuits. Furthermore, our design occupies up to 5x less area.
YodaNN: An Architecture for Ultra-Low Power Binary-Weight CNN Acceleration
Venue: arXiv cs.AR 2017
Year: 2017

Convolutional neural networks (CNNs) have revolutionized the world of computer vision over the last few years, pushing image classification beyond human accuracy. The computational effort of today's CNNs requires power-hungry parallel processors or GP-GPUs. Recent developments in CNN accelerators for system-on-chip integration have reduced energy consumption significantly. Unfortunately, even these highly optimized devices are above the power envelope imposed by mobile and deeply embedded applications and face hard limitations caused by CNN weight I/O and storage. This prevents the adoption of CNNs in future ultra-low power Internet of Things end-nodes for near-sensor analytics. Recent algorithmic and theoretical advancements enable competitive classification accuracy even when limiting CNNs to binary (+1/-1) weights during training. These new findings bring major optimization opportunities in the arithmetic core by removing the need for expensive multiplications, as well as reducing I/O bandwidth and storage. In this work, we present an accelerator optimized for binary-weight CNNs that achieves 1510 GOp/s at 1.2 V on a core area of only 1.33 MGE (Million Gate Equivalent) or 0.19 mm$^2$ and with a power dissipation of 895 μW in UMC 65 nm technology at 0.6 V. Our accelerator significantly outperforms the state-of-the-art in terms of energy and area efficiency achieving 61.2 TOp/s/W@0.6 V and 1135 GOp/s/MGE@1.2 V, respectively.
Common Codebook Millimeter Wave Beam Design: Designing Beams for Both Sounding and Communication with Uniform Planar Arrays
Venue: arXiv cs.IT 2017
Year: 2017

Fifth generation (5G) wireless networks are expected to utilize wide bandwidths available at millimeter wave (mmWave) frequencies for enhancing system throughput. However, the unfavorable channel conditions of mmWave links, e.g., higher path loss and attenuation due to atmospheric gases or water vapor, hinder reliable communications. To compensate for these severe losses, it is essential to have a multitude of antennas to generate sharp and strong beams for directional transmission. In this paper, we consider mmWave systems using uniform planar array (UPA) antennas, which effectively place more antennas on a two-dimensional grid. A hybrid beamforming setup is also considered to generate beams by combining a multitude of antennas using only a few radio frequency chains. We focus on designing a set of transmit beamformers generating beams adapted to the directional characteristics of mmWave links assuming a UPA and hybrid beamforming. We first define ideal beam patterns for UPA structures. Each beamformer is constructed to minimize the mean squared error from the corresponding ideal beam pattern. Simulation results verify that the proposed codebooks enhance beamforming reliability and data rate in mmWave systems.