OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Non-oblivious Randomized Reduction for Risk Minimization with Improved Excess Risk Guarantee
Venue: arXiv cs.LG 2016
Year: 2016

In this paper, we address learning problems for high dimensional data. Previously, oblivious random projection based approaches that project high dimensional features onto a random subspace have been used in practice for tackling high-dimensionality challenge in machine learning. Recently, various non-oblivious randomized reduction methods have been developed and deployed for solving many numerical problems such as matrix product approximation, low-rank matrix approximation, etc. However, they are less explored for the machine learning tasks, e.g., classification. More seriously, the theoretical analysis of excess risk bounds for risk minimization, an important measure of generalization performance, has not been established for non-oblivious randomized reduction methods. It therefore remains an open problem what is the benefit of using them over previous oblivious random projection based approaches. To tackle these challenges, we propose an algorithmic framework for employing non-oblivious randomized reduction method for general empirical risk minimizing in machine learning tasks, where the original high-dimensional features are projected onto a random subspace that is derived from the data with a small matrix approximation error. We then derive the first excess risk bound for the proposed non-oblivious randomized reduction approach without requiring strong assumptions on the training data. The established excess risk bound exhibits that the proposed approach provides much better generalization performance and it also sheds more insights about different randomized reduction approaches. Finally, we conduct extensive experiments on both synthetic and real-world benchmark datasets, whose dimension scales to $O(10^7)$, to demonstrate the efficacy of our proposed approach.
Spatio-temporal Models for Formal Analysis and Property-based Testing
Venue: arXiv cs.SE 2016
Year: 2016

This paper presents our ongoing work on spatio-temporal models for formal analysis and property-based testing. Our proposed framework aims at reducing the impedance mismatch between formal methods and practitioners. We introduce a set of formal methods and explain their interplay and benefits in terms of usability.
Detecting Byzantine Attacks for Gaussian Two-Way Relay System
Venue: arXiv cs.CR 2016
Year: 2016

This paper focuses on Byzantine attack detection for Gaussian two-way relay network. In this network, two source nodes communicate with each other with the help of an amplify-and-forward relay which may perform Byzantine attacks by forwarding altered symbols to the sources. For simple investigating the detectability of attacks conducted in Gaussian channels, we focus on the MA channel of the network, while assuming the BC channel is noiseless. Upon such model, we propose a attack detection scheme implemented in the sources. Specifically, we consider a open wireless propagation environment that allows the symbols, forwarded by the relay, to go through a continuous channel and arrive to the sources. With the observations of the source, we develop a detection scheme for the source by comparing the joint empirical distribution of its received and transmitted signals with the known channel statistics. The main contribution of this paper is to prove that if and only if the Gaussian relay network satisfies a non-manipulable channel condition, the proposed detection scheme can detect arbitrary attacks that allows the stochastic distributions of altered symbols to vary arbitrarily and depend on each other. No pre-shared secret or secret transmission is needed for the detection. Furthermore, we also prove that for the considered Gaussian two-way relay networks, the non-manipulable channel condition is always satisfied. This result indicates that arbitrary attacks conducted in MA Gaussian channels are detectable by only using observations, while providing a base for attack detection in more general Gaussian networks.
Memristor Threshold Logic: An Overview to Challenges and Applications
Venue: arXiv cs.ET 2016
Year: 2016

Once referred to as the missing circuit component, memristor has come long way across to be recognized and taken as important to future circuit designs. The memristor due to its ability to memorize the state, switch between different resistance level, smaller size and low leakage currents makes it useful for a wide range of intelligent memory and computing applications. This overview paper highlights broadly provides the uses of memristor in the implementation of cognitive cells for different imaging and pattern matching applications.
On the power domination number of de Bruijn and Kautz digraphs
Venue: arXiv cs.DM 2016
Year: 2016

Let $G=(V,A)$ be a directed graph without parallel arcs, and let $S\subseteq V$ be a set of vertices. Let the sequence $S=S_0\subseteq S_1\subseteq S_2\subseteq\cdots$ be defined as follows: $S_1$ is obtained from $S_0$ by adding all out-neighbors of vertices in $S_0$. For $k\geqslant 2$, $S_k$ is obtained from $S_{k-1}$ by adding all vertices $w$ such that for some vertex $v\in S_{k-1}$, $w$ is the unique out-neighbor of $v$ in $V\setminus S_{k-1}$. We set $M(S)=S_0\cup S_1\cup\cdots$, and call $S$ a \emph{power dominating set} for $G$ if $M(S)=V(G)$. The minimum cardinality of such a set is called the \emph{power domination number} of $G$. In this paper, we determine the power domination numbers of de Bruijn and Kautz digraphs.
Listen and Translate: A Proof of Concept for End-to-End Speech-to-Text Translation
Venue: arXiv cs.CL 2016
Year: 2016

This paper proposes a first attempt to build an end-to-end speech-to-text translation system, which does not use source language transcription during learning or decoding. We propose a model for direct speech-to-text translation, which gives promising results on a small French-English synthetic corpus. Relaxing the need for source language transcription would drastically change the data collection methodology in speech translation, especially in under-resourced scenarios. For instance, in the former project DARPA TRANSTAC (speech translation from spoken Arabic dialects), a large effort was devoted to the collection of speech transcripts (and a prerequisite to obtain transcripts was often a detailed transcription guide for languages with little standardized spelling). Now, if end-to-end approaches for speech-to-text translation are successful, one might consider collecting data by asking bilingual speakers to directly utter speech in the source language from target language text utterances. Such an approach has the advantage to be applicable to any unwritten (source) language.
Deterministic Indexing for Packed Strings
Venue: arXiv cs.DS 2016
Year: 2016

Given a string $S$ of length $n$, the classic string indexing problem is to preprocess $S$ into a compact data structure that supports efficient subsequent pattern queries. In the \emph{deterministic} variant the goal is to solve the string indexing problem without any randomization (at preprocessing time or query time). In the \emph{packed} variant the strings are stored with several character in a single word, giving us the opportunity to read multiple characters simultaneously. Our main result is a new string index in the deterministic \emph{and} packed setting. Given a packed string $S$ of length $n$ over an alphabet $σ$, we show how to preprocess $S$ in $O(n)$ (deterministic) time and space $O(n)$ such that given a packed pattern string of length $m$ we can support queries in (deterministic) time $O\left(m/α+ \log m + \log \log σ\right), $ where $α= w / \log σ$ is the number of characters packed in a word of size $w = Θ(\log n)$. Our query time is always at least as good as the previous best known bounds and whenever several characters are packed in a word, i.e., $\log σ\ll w$, the query times are faster.
Symmetries in the wheeled inverted pendulum mechanism
Venue: arXiv cs.SY 2016
Year: 2016

The purpose of this article is to illustrate the role of connections and symmetries in the Wheeled Inverted Pendulum (WIP) mechanism - an underactuated system with rolling constraints - popularized commercially as the Segway, and thereby arrive at a set of simpler dynamical equations that could serve as the starting point for more complex feedback control designs. The first part of the article views the nonholonomic constraints enforced by the rolling assumption as defining an Ehresmann connection on a fiber bundle. The resulting equations are the reduced Euler-Lagrange equations, which are identical to the Lagrange d'Alembert equations of motion. In the second part we explore conserved quantities, in particular, nonholonomic momenta. To do so, we first introduce the notion of a symmetry group, whose action leaves both the Lagrangian and distribution invariant. We examine two symmetry groups - $SE (2)$ and $SE(2) \times \mathbb{S}^{1}$. The first group leads to the purely kinematic case while the second gives rise to nonholonomic momentum equations.
Pseudodeterministic Constructions in Subexponential Time
Venue: arXiv cs.CC 2016
Year: 2016

We study pseudodeterministic constructions, i.e., randomized algorithms which output the same solution on most computation paths. We establish unconditionally that there is an infinite sequence $\{p_n\}_{n \in \mathbb{N}}$ of increasing primes and a randomized algorithm $A$ running in expected sub-exponential time such that for each $n$, on input $1^{|p_n|}$, $A$ outputs $p_n$ with probability $1$. In other words, our result provides a pseudodeterministic construction of primes in sub-exponential time which works infinitely often. This result follows from a much more general theorem about pseudodeterministic constructions. A property $Q \subseteq \{0,1\}^{*}$ is $γ$-dense if for large enough $n$, $|Q \cap \{0,1\}^n| \geq γ2^n$. We show that for each $c > 0$ at least one of the following holds: (1) There is a pseudodeterministic polynomial time construction of a family $\{H_n\}$ of sets, $H_n \subseteq \{0,1\}^n$, such that for each $(1/n^c)$-dense property $Q \in \mathsf{DTIME}(n^c)$ and every large enough $n$, $H_n \cap Q \neq \emptyset$; or (2) There is a deterministic sub-exponential time construction of a family $\{H'_n\}$ of sets, $H'_n \subseteq \{0,1\}^n$, such that for each $(1/n^c)$-dense property $Q \in \mathsf{DTIME}(n^c)$ and for infinitely many values of $n$, $H'_n \cap Q \neq \emptyset$. We provide further algorithmic applications that might be of independent interest. Perhaps intriguingly, while our main results are unconditional, they have a non-constructive element, arising from a sequence of applications of the hardness versus randomness paradigm.
Revisiting Winner Take All (WTA) Hashing for Sparse Datasets
Venue: arXiv cs.CV 2016
Year: 2016

WTA (Winner Take All) hashing has been successfully applied in many large scale vision applications. This hashing scheme was tailored to take advantage of the comparative reasoning (or order based information), which showed significant accuracy improvements. In this paper, we identify a subtle issue with WTA, which grows with the sparsity of the datasets. This issue limits the discriminative power of WTA. We then propose a solution for this problem based on the idea of Densification which provably fixes the issue. Our experiments show that Densified WTA Hashing outperforms Vanilla WTA both in image classification and retrieval tasks consistently and significantly.
FlowNet 2.0: Evolution of Optical Flow Estimation with Deep Networks
Venue: arXiv cs.CV 2016
Year: 2016

The FlowNet demonstrated that optical flow estimation can be cast as a learning problem. However, the state of the art with regard to the quality of the flow has still been defined by traditional methods. Particularly on small displacements and real-world data, FlowNet cannot compete with variational methods. In this paper, we advance the concept of end-to-end learning of optical flow and make it work really well. The large improvements in quality and speed are caused by three major contributions: first, we focus on the training data and show that the schedule of presenting data during training is very important. Second, we develop a stacked architecture that includes warping of the second image with intermediate optical flow. Third, we elaborate on small displacements by introducing a sub-network specializing on small motions. FlowNet 2.0 is only marginally slower than the original FlowNet but decreases the estimation error by more than 50%. It performs on par with state-of-the-art methods, while running at interactive frame rates. Moreover, we present faster variants that allow optical flow computation at up to 140fps with accuracy matching the original FlowNet.
Core Sampling Framework for Pixel Classification
Venue: arXiv cs.CV 2016
Year: 2016

The intermediate map responses of a Convolutional Neural Network (CNN) contain information about an image that can be used to extract contextual knowledge about it. In this paper, we present a core sampling framework that is able to use these activation maps from several layers as features to another neural network using transfer learning to provide an understanding of an input image. Our framework creates a representation that combines features from the test data and the contextual knowledge gained from the responses of a pretrained network, processes it and feeds it to a separate Deep Belief Network. We use this representation to extract more information from an image at the pixel level, hence gaining understanding of the whole image. We experimentally demonstrate the usefulness of our framework using a pretrained VGG-16 model to perform segmentation on the BAERI dataset of Synthetic Aperture Radar(SAR) imagery and the CAMVID dataset.
Non-volatile spin wave majority gate at the nanoscale
Venue: arXiv cs.ET 2016
Year: 2016

A spin wave majority fork-like structure with feature size of 40\,nm, is presented and investigated, through micromagnetic simulations. The structure consists of three merging out-of-plane magnetization spin wave buses and four magneto-electric cells serving as three inputs and an output. The information of the logic signals is encoded in the phase of the transmitted spin waves and subsequently stored as direction of magnetization of the magneto-electric cells upon detection. The minimum dimensions of the structure that produce an operational majority gate are identified. For all input combinations, the detection scheme employed manages to capture the majority phase result of the spin wave interference and ignore all reflection effects induced by the geometry of the structure.
Process Monitoring of Extrusion Based 3D Printing via Laser Scanning
Venue: arXiv cs.CV 2016
Year: 2016

Extrusion based 3D Printing (E3DP) is an Additive Manufacturing (AM) technique that extrudes thermoplastic polymer in order to build up components using a layerwise approach. Hereby, AM typically requires long production times in comparison to mass production processes such as Injection Molding. Failures during the AM process are often only noticed after build completion and frequently lead to part rejection because of dimensional inaccuracy or lack of mechanical performance, resulting in an important loss of time and material. A solution to improve the accuracy and robustness of a manufacturing technology is the integration of sensors to monitor and control process state-variables online. In this way, errors can be rapidly detected and possibly compensated at an early stage. To achieve this, we integrated a modular 2D laser triangulation scanner into an E3DP machine and analyzed feedback signals. A 2D laser triangulation scanner was selected here owing to the very compact size, achievable accuracy and the possibility of capturing geometrical 3D data. Thus, our implemented system is able to provide both quantitative and qualitative information. Also, in this work, first steps towards the development of a quality control loop for E3DP processes are presented and opportunities are discussed.
A simple and efficient SNN and its performance & robustness evaluation method to enable hardware implementation
Venue: arXiv cs.NE 2016
Year: 2016

Spiking Neural Networks (SNN) are more closely related to brain-like computation and inspire hardware implementation. This is enabled by small networks that give high performance on standard classification problems. In literature, typical SNNs are deep and complex in terms of network structure, weight update rules and learning algorithms. This makes it difficult to translate them into hardware. In this paper, we first develop a simple 2-layered network in software which compares with the state of the art on four different standard data-sets within SNNs and has improved efficiency. For example, it uses lower number of neurons (3 x), synapses (3.5 x) and epochs for training (30 x) for the Fisher Iris classification problem. The efficient network is based on effective population coding and synapse-neuron co-design. Second, we develop a computationally efficient (15000 x) and accurate (correlation of 0.98) method to evaluate the performance of the network without standard recognition tests. Third, we show that the method produces a robustness metric that can be used to evaluate noise tolerance.
Knowledge Representation in Graphs using Convolutional Neural Networks
Venue: arXiv cs.AI 2016
Year: 2016

Knowledge Graphs (KG) constitute a flexible representation of complex relationships between entities particularly useful for biomedical data. These KG, however, are very sparse with many missing edges (facts) and the visualisation of the mesh of interactions nontrivial. Here we apply a compositional model to embed nodes and relationships into a vectorised semantic space to perform graph completion. A visualisation tool based on Convolutional Neural Networks and Self-Organised Maps (SOM) is proposed to extract high-level insights from the KG. We apply this technique to a subset of CTD, containing interactions of compounds with human genes / proteins and show that the performance is comparable to the one obtained by structural models.
Efficient Certified RAT Verification
Venue: arXiv cs.LO 2016
Year: 2016

Clausal proofs have become a popular approach to validate the results of SAT solvers. However, validating clausal proofs in the most widely supported format (DRAT) is expensive even in highly optimized implementations. We present a new format, called LRAT, which extends the DRAT format with hints that facilitate a simple and fast validation algorithm. Checking validity of LRAT proofs can be implemented using trusted systems such as the languages supported by theorem provers. We demonstrate this by implementing two certified LRAT checkers, one in Coq and one in ACL2.
Spontaneous Proximity Clouds: Making Mobile Devices to Collaborate for Resource and Data Sharing
Venue: arXiv cs.NI 2016
Year: 2016

The base motivation of Mobile Cloud Computing was empowering mobile devices by application offloading onto powerful cloud resources. However, this goal can't entirely be reached because of the high offloading cost imposed by the long physical distance between the mobile device and the cloud. To address this issue, we propose an application offloading onto a nearby mobile cloud composed of the mobile devices in the vicinity-a Spontaneous Proximity Cloud. We introduce our proposed dynamic, ant-inspired, bi-objective offloading middleware-ACOMMA, and explain its extension to perform a close mobile application offloading. With the learning-based offloading decision-making process of ACOMMA, combined to the collaborative resource sharing, the mobile devices can cooperate for decision cache sharing. We evaluate the performance of ACOMMA in collaborative mode with real benchmarks Face Recognition and Monte-Carlo algorithms-and achieve 50% execution time gain.
A Universal Multi-Hierarchy Figure-of-Merit for On-Chip Computing and Communications
Venue: arXiv cs.ET 2016
Year: 2016

Continuing demands for increased compute efficiency and communication bandwidth have led to the development of novel interconnect technologies with the potential to outperform conventional electrical interconnects. With a plurality of interconnect technologies to include electronics, photonics, plasmonics, and hybrids thereof, the simple approach of counting on-chip devices to capture performance is insufficient. While some efforts have been made to capture the performance evolution more accurately, they eventually deviate from the observed development pace. Thus, a holistic figure of merit (FOM) is needed to adequately compare these recent technology paradigms. Here we introduce the Capability-to-Latency-Energy-Amount-Resistance (CLEAR) FOM derived from device and link performance criteria of both active optoelectronic devices and passive components alike. As such CLEAR incorporates communication delay, energy efficiency, on-chip scaling and economic cost. We show that CLEAR accurately describes compute development including most recent machines. Since this FOM is derived bottom-up, we demonstrate remarkable adaptability to applications ranging from device-level to network and system-level. Applying CLEAR to benchmark device, link, and network performance against fundamental physical compute and communication limits shows that photonics is competitive even for fractions of the die-size, thus making a case for on-chip optical interconnects.
Bridging Medical Data Inference to Achilles Tendon Rupture Rehabilitation
Venue: arXiv cs.LG 2016
Year: 2016

Imputing incomplete medical tests and predicting patient outcomes are crucial for guiding the decision making for therapy, such as after an Achilles Tendon Rupture (ATR). We formulate the problem of data imputation and prediction for ATR relevant medical measurements into a recommender system framework. By applying MatchBox, which is a collaborative filtering approach, on a real dataset collected from 374 ATR patients, we aim at offering personalized medical data imputation and prediction. In this work, we show the feasibility of this approach and discuss potential research directions by conducting initial qualitative evaluations.
Geometric Decomposition of Feed Forward Neural Networks
Venue: arXiv cs.NE 2016
Year: 2016

There have been several attempts to mathematically understand neural networks and many more from biological and computational perspectives. The field has exploded in the last decade, yet neural networks are still treated much like a black box. In this work we describe a structure that is inherent to a feed forward neural network. This will provide a framework for future work on neural networks to improve training algorithms, compute the homology of the network, and other applications. Our approach takes a more geometric point of view and is unlike other attempts to mathematically understand neural networks that rely on a functional perspective.