OpenRaiser/Intern-Atlas huggingface dataset:
FINN: A Framework for Fast, Scalable Binarized Neural Network Inference
Venue: arXiv cs.CV 2016
Year: 2016

Research has shown that convolutional neural networks contain significant redundancy, and high classification accuracy can be obtained even when weights and activations are reduced from floating point to binary values. In this paper, we present FINN, a framework for building fast and flexible FPGA accelerators using a flexible heterogeneous streaming architecture. By utilizing a novel set of optimizations that enable efficient mapping of binarized neural networks to hardware, we implement fully connected, convolutional and pooling layers, with per-layer compute resources being tailored to user-provided throughput requirements. On a ZC706 embedded FPGA platform drawing less than 25 W total system power, we demonstrate up to 12.3 million image classifications per second with 0.31 μs latency on the MNIST dataset with 95.8% accuracy, and 21906 image classifications per second with 283 μs latency on the CIFAR-10 and SVHN datasets with respectively 80.1% and 94.9% accuracy. To the best of our knowledge, ours are the fastest classification rates reported to date on these benchmarks.
Supercritical Space-Width Trade-offs for Resolution
Venue: arXiv cs.CC 2016
Year: 2016

We show that there are CNF formulas which can be refuted in resolution in both small space and small width, but for which any small-width proof must have space exceeding by far the linear worst-case upper bound. This significantly strengthens the space-width trade-offs in [Ben-Sasson '09]}, and provides one more example of trade-offs in the "supercritical" regime above worst case recently identified by [Razborov '16]. We obtain our results by using Razborov's new hardness condensation technique and combining it with the space lower bounds in [Ben-Sasson and Nordstrom '08].
"420 Friendly": Revealing Marijuana Use via Craigslist Rental Ads
Venue: arXiv cs.CY 2016
Year: 2016

Recent studies have shown that information mined from Craigslist can be used for informing public health policy or monitoring risk behavior. This paper presents a text-mining method for conducting public health surveillance of marijuana use concerns in the U.S. using online classified ads in Craigslist. We collected more than 200 thousands of rental ads in the housing categories in Craigslist and devised text-mining methods for efficiently and accurately extract rental ads associated with concerns about the uses of marijuana in different states across the U.S. We linked the extracted ads to their geographic locations and computed summary statistics of the ads having marijuana use concerns. Our data is then compared with the State Marijuana Laws Map published by the U.S. government and marijuana related keywords search in Google to verify our collected data with respect to the demographics of marijuana use concerns. Our data not only indicates strong correlations between Craigslist ads, Google search and the State Marijuana Laws Map in states where marijuana uses are legal, but also reveals some hidden world of marijuana use concerns in other states where marijuana use is illegal. Our approach can be utilized as a marijuana surveillance tool for policy makers to develop public health policy and regulations.
Experimental prototype of a spin-wave majority gate
Venue: arXiv cs.ET 2016
Year: 2016

Featuring low heat dissipation, devices based on spin-wave logic gates promise to comply with increasing future requirements in information processing. In this work, we present the experimental realization of a majority gate based on the interference of spin waves in an Yttrium-Iron-Garnet-based waveguiding structure. This logic device features a three-input combiner with the logic information encoded in the phase of the spin waves. We show that the phase of the output signal represents the majority of the phase of the input signals. A switching time of about 10 ns in the prototype device provides evidence for the ability of sub-nanosecond data processing in future down-scaled devices.
Understanding Image and Text Simultaneously: a Dual Vision-Language Machine Comprehension Task
Venue: arXiv cs.CL 2016
Year: 2016

We introduce a new multi-modal task for computer systems, posed as a combined vision-language comprehension challenge: identifying the most suitable text describing a scene, given several similar options. Accomplishing the task entails demonstrating comprehension beyond just recognizing "keywords" (or key-phrases) and their corresponding visual concepts. Instead, it requires an alignment between the representations of the two modalities that achieves a visually-grounded "understanding" of various linguistic elements and their dependencies. This new task also admits an easy-to-compute and well-studied metric: the accuracy in detecting the true target among the decoys. The paper makes several contributions: an effective and extensible mechanism for generating decoys from (human-created) image captions; an instance of applying this mechanism, yielding a large-scale machine comprehension dataset (based on the COCO images and captions) that we make publicly available; human evaluation results on this dataset, informing a performance upper-bound; and several baseline and competitive learning approaches that illustrate the utility of the proposed task and dataset in advancing both image and language comprehension. We also show that, in a multi-task learning setting, the performance on the proposed task is positively correlated with the end-to-end task of image captioning.
"What is Relevant in a Text Document?": An Interpretable Machine Learning Approach
Venue: arXiv cs.CL 2016
Year: 2016

Text documents can be described by a number of abstract concepts such as semantic category, writing style, or sentiment. Machine learning (ML) models have been trained to automatically map documents to these abstract concepts, allowing to annotate very large text collections, more than could be processed by a human in a lifetime. Besides predicting the text's category very accurately, it is also highly desirable to understand how and why the categorization process takes place. In this paper, we demonstrate that such understanding can be achieved by tracing the classification decision back to individual words using layer-wise relevance propagation (LRP), a recently developed technique for explaining predictions of complex non-linear classifiers. We train two word-based ML models, a convolutional neural network (CNN) and a bag-of-words SVM classifier, on a topic categorization task and adapt the LRP method to decompose the predictions of these models onto words. Resulting scores indicate how much individual words contribute to the overall classification decision. This enables one to distill relevant information from text documents without an explicit semantic information extraction step. We further use the word-wise relevance scores for generating novel vector-based document representations which capture semantic information. Based on these document vectors, we introduce a measure of model explanatory power and show that, although the SVM and CNN models perform similarly in terms of classification accuracy, the latter exhibits a higher level of explainability which makes it more comprehensible for humans and potentially more useful for other applications.
Information-Centric Wireless Networks with Virtualization and D2D Communications
Venue: arXiv cs.NI 2016
Year: 2016

Wireless network virtualization and information-centric networking (ICN) are two promising technologies for next generation wireless networks. Although some excellent works have focused on these two technologies, device-to-device (D2D) communications have not beeen investigated in information-centric virtualized cellular networks. Meanwhile, content caching in mobile devices has attracted great attentions due to the saved backhaul consumption or reduced transmission latency in D2D-assisted cellular networks. However, when it comes to the multi-operator scenario, the direct content sharing between different operators via D2D communications is typically infeasible. In this article, we propose a novel information-centric virtualized cellular network framework with D2D communications, enabling not only content caching in the air, but also inter-operator content sharing between mobile devices. Moreover, we describe the key components in the proposed framework, and present the interactions among them. In addition, we incorporate and formulate the content caching strategies in resource allocation optimization, to maximize the total utility of mobile virtual network operators (MVNOs) through caching popular contents in mobile devices. Simulations results demonstrate the effectiveness of the proposed framework and scheme with different system parameters.
Geo-Location Based Access for Vehicular Communications: Analysis and Optimization via Stochastic Geometry
Venue: arXiv cs.IT 2016
Year: 2016

Delivery of broadcast messages among vehicles for safety purposes, which is known as one of the key ingredients of Intelligent Transportation Systems (ITS), requires an efficient Medium Access Control (MAC) that provides low average delay and high reliability. To this end, a Geo-Location Based Access (GLOC) for vehicles has been proposed for Vehicle-to-Vehicle (V2V) communications, aiming at maximizing the distance of co-channel transmitters while preserving a low latency when accessing the resources. In this paper we analyze, with the aid of stochastic geometry, the delivery of periodic and non-periodic broadcast messages with GLOC, taking into account path loss and fading as well as the random locations of transmitting vehicles. Analytical results include the average interference, average Binary Rate (BR), capture probability, i.e., the probability of successful message transmission, and Energy Efficiency (EE). Mathematical analysis reveals interesting insights about the system performance, which are validated thought extensive Monte Carlo simulations. In particular, it is shown that the capture probability is an increasing function with exponential dependence with respect to the transmit power and it is demonstrated that an arbitrary high capture probability can be achieved, as long as the number of access resources is high enough. Finally, to facilitate the system-level design of GLOC, the optimum transmit power is derived, which leads to a maximal EE subject to a given constraint in the capture probability.
Push Recovery of a Humanoid Robot Based on Model Predictive Control and Capture Point
Venue: arXiv cs.RO 2016
Year: 2016

The three bio-inspired strategies that have been used for balance recovery of biped robots are the ankle, hip and stepping Strategies. However, there are several cases for a biped robot where stepping is not possible, e. g. when the available contact surfaces are limited. In this situation, the balance recovery by modulating the angular momentum of the upper body (Hip-strategy) or the Zero Moment Point (ZMP) (Ankle strategy) is essential. In this paper, a single Model Predictive Control (MPC) scheme is employed for controlling the Capture Point (CP) to a desired position by modulating both the ZMP and the Centroidal Moment Pivot (CMP). The goal of the proposed controller is to control the CP, employing the CMP when the CP is out of the support polygon, and/or the ZMP when the CP is inside the support polygon. The proposed algorithm is implemented on an abstract model of the SURENA III humanoid robot. Obtained results show the effectiveness of the proposed approach in the presence of severe pushes, even when the support polygon is shrunken to a point or a line.
On the complete width and edge clique cover problems
Venue: arXiv cs.DM 2016
Year: 2016

A complete graph is the graph in which every two vertices are adjacent. For a graph $G=(V,E)$, the complete width of $G$ is the minimum $k$ such that there exist $k$ independent sets $\mathtt{N}_i\subseteq V$, $1\le i\le k$, such that the graph $G'$ obtained from $G$ by adding some new edges between certain vertices inside the sets $\mathtt{N}_i$, $1\le i\le k$, is a complete graph. The complete width problem is to decide whether the complete width of a given graph is at most $k$ or not. In this paper we study the complete width problem. We show that the complete width problem is NP-complete on $3K_2$-free bipartite graphs and polynomially solvable on $2K_2$-free bipartite graphs and on $(2K_2,C_4)$-free graphs. As a by-product, we obtain the following new results: the edge clique cover problem is NP-complete on $\overline{3K_2}$-free co-bipartite graphs and polynomially solvable on $C_4$-free co-bipartite graphs and on $(2K_2, C_4)$-free graphs. We also give a characterization for $k$-probe complete graphs which implies that the complete width problem admits a kernel of at most $2^k$ vertices. This provides another proof for the known fact that the edge clique cover problem admits a kernel of at most $2^k$ vertices. Finally we determine all graphs of small complete width $k\le 3$.
Improving Human-Machine Cooperative Visual Search With Soft Highlighting
Venue: arXiv cs.HC 2016
Year: 2016

Advances in machine learning have produced systems that attain human-level performance on certain visual tasks, e.g., object identification. Nonetheless, other tasks requiring visual expertise are unlikely to be entrusted to machines for some time, e.g., satellite and medical imagery analysis. We describe a human-machine cooperative approach to visual search, the aim of which is to outperform either human or machine acting alone. The traditional route to augmenting human performance with automatic classifiers is to draw boxes around regions of an image deemed likely to contain a target. Human experts typically reject this type of hard highlighting. We propose instead a soft highlighting technique in which the saliency of regions of the visual field is modulated in a graded fashion based on classifier confidence level. We report on experiments with both synthetic and natural images showing that soft highlighting achieves a performance synergy surpassing that attained by hard highlighting.
Brain-Swarm Interface (BSI): Controlling a Swarm of Robots with Brain and Eye Signals from an EEG Headset
Venue: arXiv cs.RO 2016
Year: 2016

This work presents a novel marriage of Swarm Robotics and Brain Computer Interface technology to produce an interface which connects a user to a swarm of robots. The proposed interface enables the user to control the swarm's size and motion employing just thoughts and eye movements. The thoughts and eye movements are recorded as electrical signals from the scalp by an off-the-shelf Electroencephalogram (EEG) headset. Signal processing techniques are used to filter out noise and decode the user's eye movements from raw signals, while a Hidden Markov Model technique is employed to decipher the user's thoughts from filtered signals. The dynamics of the robots are controlled using a swarm controller based on potential fields. The shape and motion parameters of the potential fields are modulated by the human user through the brain-swarm interface to move the robots. The method is demonstrated experimentally with a human controlling a swarm of three M3pi robots in a laboratory environment, as well as controlling a swarm of 128 robots in a computer simulation.
Application-aware Retiming of Accelerators: A High-level Data-driven Approach
Venue: arXiv cs.AR 2016
Year: 2016

Flexibility at hardware level is the main driving force behind adaptive systems whose aim is to realise microarhitecture deconfiguration 'online'. This feature allows the software/hardware stack to tolerate drastic changes of the workload in data centres. With emerge of FPGA reconfigurablity this technology is becoming a mainstream computing paradigm. Adaptivity is usually accompanied by the high-level tools to facilitate multi-dimensional space exploration. An essential aspect in this space is memory orchestration where on-chip and off-chip memory distribution significantly influences the architecture in coping with the critical spatial and timing constraints, e.g. Place and Route. This paper proposes a memory smart technique for a particular class of adaptive systems: Elastic Circuits which enjoy slack elasticity at fine level of granularity. We explore retiming of a set of popular benchmarks via investigating the memory distribution within and among accelerators. The area, performance and power patterns are adopted by our high-level synthesis framework, with respect to the behaviour of the input descriptions, to improve the quality of the synthesised elastic circuits.
An Improved Homomorphism Preservation Theorem From Lower Bounds in Circuit Complexity
Venue: arXiv cs.CC 2016
Year: 2016

Previous work of the author [39] showed that the Homomorphism Preservation Theorem of classical model theory remains valid when its statement is restricted to finite structures. In this paper, we give a new proof of this result via a reduction to lower bounds in circuit complexity, specifically on the AC$^0$ formula size of the colored subgraph isomorphism problem. Formally, we show the following: if a first-order sentence $Φ$ of quantifier-rank $k$ is preserved under homomorphisms on finite structures, then it is equivalent on finite structures to an existential-positive sentence $Ψ$ of quantifier-rank $k^{O(1)}$. Quantitatively, this improves the result of [39], where the upper bound on the quantifier-rank of $Ψ$ is a non-elementary function of $k$.
Neighborhood complexity and kernelization for nowhere dense classes of graphs
Venue: arXiv cs.DM 2016
Year: 2016

We prove that whenever $G$ is a graph from a nowhere dense graph class $\mathcal{C}$, and $A$ is a subset of vertices of $G$, then the number of subsets of $A$ that are realized as intersections of $A$ with $r$-neighborhoods of vertices of $G$ is at most $f(r,ε)\cdot |A|^{1+ε}$, where $r$ is any positive integer, $ε$ is any positive real, and $f$ is a function that depends only on the class $\mathcal{C}$. This yields a characterization of nowhere dense classes of graphs in terms of neighborhood complexity, which answers a question posed by Reidl et al. As an algorithmic application of the above result, we show that for every fixed $r$, the parameterized Distance-$r$ Dominating Set problem admits an almost linear kernel on any nowhere dense graph class. This proves a conjecture posed by Drange et al., and shows that the limit of parameterized tractability of Distance-$r$ Dominating Set on subgraph-closed graph classes lies exactly on the boundary between nowhere denseness and somewhere denseness.
A Simple Semantics for Haskell Overloading
Venue: arXiv cs.PL 2016
Year: 2016

As originally proposed, type classes provide overloading and ad-hoc definition, but can still be understood (and implemented) in terms of strictly parametric calculi. This is not true of subsequent extensions of type classes. Functional dependencies and equality constraints allow the satisfiability of predicates to refine typing; this means that the interpretations of equivalent qualified types may not be interconvertible. Overlapping instances and instance chains allow predicates to be satisfied without determining the implementations of their associated class methods, introducing truly non-parametric behavior. We propose a new approach to the semantics of type classes, interpreting polymorphic expressions by the behavior of each of their ground instances, but without requiring that those behaviors be parametrically determined. We argue that this approach both matches the intuitive meanings of qualified types and accurately models the behavior of programs
Globally Optimal Object Tracking with Fully Convolutional Networks
Venue: arXiv cs.CV 2016
Year: 2016

Tracking is one of the most important but still difficult tasks in computer vision and pattern recognition. The main difficulties in the tracking field are appearance variation and occlusion. Most traditional tracking methods set the parameters or templates to track target objects in advance and should be modified accordingly. Thus, we propose a new and robust tracking method using a Fully Convolutional Network (FCN) to obtain an object probability map and Dynamic Programming (DP) to seek the globally optimal path through all frames of video. Our proposed method solves the object appearance variation problem with the use of a FCN and deals with occlusion by DP. We show that our method is effective in tracking various single objects through video frames.
A Distributed Algorithm for Quality-of-Service Provisioning in Multihop Networks
Venue: arXiv cs.NI 2016
Year: 2016

We present a distributed algorithm for joint power control, routing and scheduling in multihop wireless networks. The algorithm also provides for Quality of Service (QoS) guarantees, namely, end-to-end mean delay guarantees and hard deadline guarantees, for different users. It is easily implementable and works by giving local dynamic priority to flows requiring QoS, the priority being a function of the queue length at the nodes. We provide theoretical bounds for the stability properties of the algorithm. We also compare the performance of the algorithm with other existing algorithms by means of extensive simulations, and demonstrate its efficacy in providing QoS on demand.
End-to-End Data Visualization by Metric Learning and Coordinate Transformation
Venue: arXiv cs.CV 2016
Year: 2016

This paper presents a deep nonlinear metric learning framework for data visualization on an image dataset. We propose the Triangular Similarity and prove its equivalence to the Cosine Similarity in measuring a data pair. Based on this novel similarity, a geometrically motivated loss function - the triangular loss - is then developed for optimizing a metric learning system comprising two identical CNNs. It is shown that this deep nonlinear system can be efficiently trained by a hybrid algorithm based on the conventional backpropagation algorithm. More interestingly, benefiting from classical manifold learning theories, the proposed system offers two different views to visualize the outputs, the second of which provides better classification results than the state-of-the-art methods in the visualizable spaces.
Robust LSTM-Autoencoders for Face De-Occlusion in the Wild
Venue: arXiv cs.CV 2016
Year: 2016

Face recognition techniques have been developed significantly in recent years. However, recognizing faces with partial occlusion is still challenging for existing face recognizers which is heavily desired in real-world applications concerning surveillance and security. Although much research effort has been devoted to developing face de-occlusion methods, most of them can only work well under constrained conditions, such as all the faces are from a pre-defined closed set. In this paper, we propose a robust LSTM-Autoencoders (RLA) model to effectively restore partially occluded faces even in the wild. The RLA model consists of two LSTM components, which aims at occlusion-robust face encoding and recurrent occlusion removal respectively. The first one, named multi-scale spatial LSTM encoder, reads facial patches of various scales sequentially to output a latent representation, and occlusion-robustness is achieved owing to the fact that the influence of occlusion is only upon some of the patches. Receiving the representation learned by the encoder, the LSTM decoder with a dual channel architecture reconstructs the overall face and detects occlusion simultaneously, and by feat of LSTM, the decoder breaks down the task of face de-occlusion into restoring the occluded part step by step. Moreover, to minimize identify information loss and guarantee face recognition accuracy over recovered faces, we introduce an identity-preserving adversarial training scheme to further improve RLA. Extensive experiments on both synthetic and real datasets of faces with occlusion clearly demonstrate the effectiveness of our proposed RLA in removing different types of facial occlusion at various locations. The proposed method also provides significantly larger performance gain than other de-occlusion methods in promoting recognition performance over partially-occluded faces.