OpenRaiser/Intern-Atlas huggingface dataset:
Random active path model of deep neural networks with diluted binary synapses
Venue: arXiv cs.LG 2018
Year: 2018

Deep learning has become a powerful and popular tool for a variety of machine learning tasks. However, it is challenging to understand the mechanism of deep learning from a theoretical perspective. In this work, we propose a random active path model to study collective properties of deep neural networks with binary synapses, under the removal perturbation of connections between layers. In the model, the path from input to output is randomly activated, and the corresponding input unit constrains the weights along the path into the form of a $p$-weight interaction glass model. A critical value of the perturbation is observed to separate a spin glass regime from a paramagnetic regime, with the transition being of the first order. The paramagnetic phase is conjectured to have a poor generalization performance.
Derivate-based Component-Trees for Multi-Channel Image Segmentation
Venue: arXiv cs.CV 2018
Year: 2018

We introduce the concept of derivate-based component-trees for images with an arbitrary number of channels. The approach is a natural extension of the classical component-tree devoted to gray-scale images. The similar structure enables the translation of many gray-level image processing techniques based on the component-tree to hyperspectral and color images. As an example application, we present an image segmentation approach that extracts Maximally Stable Homogeneous Regions (MSHR). The approach very similar to MSER but can be applied to images with an arbitrary number of channels. As opposed to MSER, our approach implicitly segments regions with are both lighter and darker than their background for gray-scale images and can be used in OCR applications where MSER will fail. We introduce a local flooding-based immersion for the derivate-based component-tree construction which is linear in the number of pixels. In the experiments, we show that the runtime scales favorably with an increasing number of channels and may improve algorithms which build on MSER.
Approximate Nash Equilibria in Partially Observed Stochastic Games with Mean-Field Interactions
Venue: arXiv cs.SY 2018
Year: 2018

Establishing the existence of Nash equilibria for partially observed stochastic dynamic games is known to be quite challenging, with the difficulties stemming from the noisy nature of the measurements available to individual players (agents) and the decentralized nature of this information. When the number of players is sufficiently large and the interactions among agents is of the mean-field type, one way to overcome this challenge is to investigate the infinite-population limit of the problem, which leads to a mean-field game. In this paper, we consider discrete-time partially observed mean-field games with infinite-horizon discounted cost criteria. Using the technique of converting the original partially observed stochastic control problem to a fully observed one on the belief space and the dynamic programming principle, we establish the existence of Nash equilibria for these game models under very mild technical conditions. Then, we show that the mean-field equilibrium policy, when adopted by each agent, forms an approximate Nash equilibrium for games with sufficiently many agents.
Supervised Learning of Universal Sentence Representations from Natural Language Inference Data
Venue: arXiv cs.CL 2018
Year: 2018

Many modern NLP systems rely on word embeddings, previously trained in an unsupervised manner on large corpora, as base features. Efforts to obtain embeddings for larger chunks of text, such as sentences, have however not been so successful. Several attempts at learning unsupervised representations of sentences have not reached satisfactory enough performance to be widely adopted. In this paper, we show how universal sentence representations trained using the supervised data of the Stanford Natural Language Inference datasets can consistently outperform unsupervised methods like SkipThought vectors on a wide range of transfer tasks. Much like how computer vision uses ImageNet to obtain features, which can then be transferred to other tasks, our work tends to indicate the suitability of natural language inference for transfer learning to other NLP tasks. Our encoder is publicly available.
Identifying combinations of tetrahedra into hexahedra: a vertex based strategy
Venue: arXiv cs.CG 2018
Year: 2018

Indirect hex-dominant meshing methods rely on the detection of adjacent tetrahedra an algorithm that performs this identification and builds the set of all possible combinations of tetrahedral elements of an input mesh T into hexahedra, prisms, or pyramids. All identified cells are valid for engineering analysis. First, all combinations of eight/six/five vertices whose connectivity in T matches the connectivity of a hexahedron/prism/pyramid are computed. The subset of tetrahedra of T triangulating each potential cell is then determined. Quality checks allow to early discard poor quality cells and to dramatically improve the efficiency of the method. Each potential hexahedron/prism/pyramid is computed only once. Around 3 millions potential hexahedra are computed in 10 seconds on a laptop. We finally demonstrate that the set of potential hexes built by our algorithm is significantly larger than those built using predefined patterns of subdivision of a hexahedron in tetrahedral elements.
Linear Network Coding for Two-Unicast-$Z$ Networks: A Commutative Algebraic Perspective and Fundamental Limits
Venue: arXiv cs.IT 2018
Year: 2018

We consider a two-unicast-$Z$ network over a directed acyclic graph of unit capacitated edges; the two-unicast-$Z$ network is a special case of two-unicast networks where one of the destinations has apriori side information of the unwanted (interfering) message. In this paper, we settle open questions on the limits of network coding for two-unicast-$Z$ networks by showing that the generalized network sharing bound is not tight, vector linear codes outperform scalar linear codes, and non-linear codes outperform linear codes in general. We also develop a commutative algebraic approach to deriving linear network coding achievability results, and demonstrate our approach by providing an alternate proof to the previous results of C. Wang et. al., I. Wang et. al. and Shenvi et. al. regarding feasibility of rate $(1,1)$ in the network.
A neural network system for transformation of regional cuisine style
Venue: arXiv cs.CY 2018
Year: 2018

We propose a novel system which can transform a recipe into any selected regional style (e.g., Japanese, Mediterranean, or Italian). This system has two characteristics. First the system can identify the degree of regional cuisine style mixture of any selected recipe and visualize such regional cuisine style mixtures using barycentric Newton diagrams. Second, the system can suggest ingredient substitutions through an extended word2vec model, such that a recipe becomes more authentic for any selected regional cuisine style. Drawing on a large number of recipes from Yummly, an example shows how the proposed system can transform a traditional Japanese recipe, Sukiyaki, into French style.
R2-D2: ColoR-inspired Convolutional NeuRal Network (CNN)-based AndroiD Malware Detections
Venue: arXiv cs.CR 2018
Year: 2018

The influence of Deep Learning on image identification and natural language processing has attracted enormous attention globally. The convolution neural network that can learn without prior extraction of features fits well in response to the rapid iteration of Android malware. The traditional solution for detecting Android malware requires continuous learning through pre-extracted features to maintain high performance of identifying the malware. In order to reduce the manpower of feature engineering prior to the condition of not to extract pre-selected features, we have developed a coloR-inspired convolutional neuRal networks (CNN)-based AndroiD malware Detection (R2-D2) system. The system can convert the bytecode of classes.dex from Android archive file to rgb color code and store it as a color image with fixed size. The color image is input to the convolutional neural network for automatic feature extraction and training. The data was collected from Jan. 2017 to Aug 2017. During the period of time, we have collected approximately 2 million of benign and malicious Android apps for our experiments with the help from our research partner Leopard Mobile Inc. Our experiment results demonstrate that the proposed system has accurate security analysis on contracts. Furthermore, we keep our research results and experiment materials on http://R2D2.TWMAN.ORG.
Zampa's systems theory: a comprehensive theory of measurement in dynamic systems
Venue: arXiv cs.OH 2018
Year: 2018

The article outlines in memoriam Prof. Pavel Zampa's concepts of system theory which enable to devise a measurement in dynamic systems independently of the particular system behaviour. From the point of view of Zampa's theory, terms like system time, system attributes, system link, system element, input, output, subsystems, and state variables are defined. In Conclusions, Zampa's theory is discussed together with another mathematical approaches of qualitative dynamics known since the 19th century. In Appendices, we present applications of Zampa's technical approach to measurement of complex dynamical (chemical and biological) systems at the Institute of Complex Systems, University of South Bohemia in Ceske Budejovice.
Adapting a General Purpose Social Robot for Paediatric Rehabilitation through In-situ Design
Venue: arXiv cs.HC 2018
Year: 2018

Socially Assistive Robots (SARs) offer great promise for improving outcomes in paediatric rehabilitation. However, the design of software and interactive capabilities for SARs must be carefully considered in the context of their intended clinical use. While previous work has explored specific roles and functionalities to support paediatric rehabilitation, few have considered the design of such capabilities in the context of ongoing clinical deployment. In this paper we present a two-phase In-situ design process for SARs in health care, emphasising stakeholder engagement and on-site development. We explore this in the context of developing the humanoid social robot NAO as a socially assistive rehabilitation aid for children with cerebral palsy. We present and evaluate our design process, outcomes achieved, and preliminary results from ongoing clinical testing with 9 patients and 5 therapists over 14 sessions. We argue that our in-situ Design methodology has been central to the rapid and successful deployment of our system.
FAST$^2$: an Intelligent Assistant for Finding Relevant Papers
Venue: arXiv cs.SE 2018
Year: 2018

Literature reviews are essential for any researcher trying to keep up to date with the burgeoning software engineering literature. FAST$^2$ is a novel tool for reducing the effort required for conducting literature reviews by assisting the researchers to find the next promising paper to read (among a set of unread papers). This paper describes FAST$^2$ and tests it on four large software engineering literature reviews conducted by Wahono (2015), Hall (2012), Radjenović (2013) and Kitchenham (2017). We find that FAST$^2$ is a faster and robust tool to assist researcher finding relevant SE papers which can compensate for the errors made by humans during the review process. The effectiveness of FAST$^2$ can be attributed to three key innovations: (1) a novel way of applying external domain knowledge (a simple two or three keyword search) to guide the initial selection of papers---which helps to find relevant research papers faster with less variances; (2) an estimator of the number of remaining relevant papers yet to be found---which in practical settings can be used to decide if the reviewing process needs to be terminated; (3) a novel self-correcting classification algorithm---automatically corrects itself, in cases where the researcher wrongly classifies a paper.
A New Approach to GraphMaps, a System Browsing Large Graphs as Interactive Maps
Venue: arXiv cs.CG 2018
Year: 2018

A GraphMaps is a system that visualizes a graph using zoom levels, which is similar to a geographic map visualization. GraphMaps reveals the structural properties of the graph and enables users to explore the graph in a natural way by using the standard zoom and pan operations. The available implementation of GraphMaps faces many challenges such as the number of zoom levels may be large, nodes may be unevenly distributed to different levels, shared edges may create ambiguity due to the selection of multiple nodes. In this paper, we develop an algorithmic framework to construct GraphMaps from any given mesh (generated from a 2D point set), and for any given number of zoom levels. We demonstrate our approach introducing competition mesh, which is simple to construct, has a low dilation and high angular resolution. We present an algorithm for assigning nodes to zoom levels that minimizes the change in the number of nodes on visible on the screen while the user zooms in and out between the levels. We think that keeping this change small facilitates smooth browsing of the graph. We also propose new node selection techniques to cope with some of the challenges of the GraphMaps approach.
Counting perfect matchings and the switch chain
Venue: arXiv cs.DM 2018
Year: 2018

We examine the problem of exactly or approximately counting all perfect matchings in hereditary classes of nonbipartite graphs. In particular, we consider the switch Markov chain of Diaconis, Graham and Holmes. We determine the largest hereditary class for which the chain is ergodic, and define a large new hereditary class of graphs for which it is rapidly mixing. We go on to show that the chain has exponential mixing time for a slightly larger class. We also examine the question of ergodicity of the switch chain in a arbitrary graph. Finally, we give exact counting algorithms for three classes.
Scheduling Distributed Resources in Heterogeneous Private Clouds
Venue: arXiv cs.PF 2018
Year: 2018

We first consider the static problem of allocating resources to ( i.e. , scheduling) multiple distributed application framework s, possibly with different priorities and server preferences , in a private cloud with heterogeneous servers. Several fai r scheduling mechanisms have been proposed for this purpose. We extend pr ior results on max-min and proportional fair scheduling to t his constrained multiresource and multiserver case for generi c fair scheduling criteria. The task efficiencies (a metric r elated to proportional fairness) of max-min fair allocations found b y progressive filling are compared by illustrative examples . They show that "server specific" fairness criteria and those that are b ased on residual (unreserved) resources are more efficient.
End-to-End Cross-Modality Retrieval with CCA Projections and Pairwise Ranking Loss
Venue: arXiv cs.IR 2018
Year: 2018

Cross-modality retrieval encompasses retrieval tasks where the fetched items are of a different type than the search query, e.g., retrieving pictures relevant to a given text query. The state-of-the-art approach to cross-modality retrieval relies on learning a joint embedding space of the two modalities, where items from either modality are retrieved using nearest-neighbor search. In this work, we introduce a neural network layer based on Canonical Correlation Analysis (CCA) that learns better embedding spaces by analytically computing projections that maximize correlation. In contrast to previous approaches, the CCA Layer (CCAL) allows us to combine existing objectives for embedding space learning, such as pairwise ranking losses, with the optimal projections of CCA. We show the effectiveness of our approach for cross-modality retrieval on three different scenarios (text-to-image, audio-sheet-music and zero-shot retrieval), surpassing both Deep CCA and a multi-view network using freely learned projections optimized by a pairwise ranking loss, especially when little training data is available (the code for all three methods is released at: https://github.com/CPJKU/cca_layer).
What are the Receptive, Effective Receptive, and Projective Fields of Neurons in Convolutional Neural Networks?
Venue: arXiv cs.CV 2018
Year: 2018

In this work, we explain in detail how receptive fields, effective receptive fields, and projective fields of neurons in different layers, convolution or pooling, of a Convolutional Neural Network (CNN) are calculated. While our focus here is on CNNs, the same operations, but in the reverse order, can be used to calculate these quantities for deconvolutional neural networks. These are important concepts, not only for better understanding and analyzing convolutional and deconvolutional networks, but also for optimizing their performance in real-world applications.
Espresso: Efficient Forward Propagation for BCNNs
Venue: arXiv cs.DC 2018
Year: 2018

There are many applications scenarios for which the computational performance and memory footprint of the prediction phase of Deep Neural Networks (DNNs) needs to be optimized. Binary Neural Networks (BDNNs) have been shown to be an effective way of achieving this objective. In this paper, we show how Convolutional Neural Networks (CNNs) can be implemented using binary representations. Espresso is a compact, yet powerful library written in C/CUDA that features all the functionalities required for the forward propagation of CNNs, in a binary file less than 400KB, without any external dependencies. Although it is mainly designed to take advantage of massive GPU parallelism, Espresso also provides an equivalent CPU implementation for CNNs. Espresso provides special convolutional and dense layers for BCNNs, leveraging bit-packing and bit-wise computations for efficient execution. These techniques provide a speed-up of matrix-multiplication routines, and at the same time, reduce memory usage when storing parameters and activations. We experimentally show that Espresso is significantly faster than existing implementations of optimized binary neural networks ($\approx$ 2 orders of magnitude). Espresso is released under the Apache 2.0 license and is available at http://github.com/fpeder/espresso.
DeepMasterPrints: Generating MasterPrints for Dictionary Attacks via Latent Variable Evolution
Venue: arXiv cs.CV 2018
Year: 2018

Recent research has demonstrated the vulnerability of fingerprint recognition systems to dictionary attacks based on MasterPrints. MasterPrints are real or synthetic fingerprints that can fortuitously match with a large number of fingerprints thereby undermining the security afforded by fingerprint systems. Previous work by Roy et al. generated synthetic MasterPrints at the feature-level. In this work we generate complete image-level MasterPrints known as DeepMasterPrints, whose attack accuracy is found to be much superior than that of previous methods. The proposed method, referred to as Latent Variable Evolution, is based on training a Generative Adversarial Network on a set of real fingerprint images. Stochastic search in the form of the Covariance Matrix Adaptation Evolution Strategy is then used to search for latent input variables to the generator network that can maximize the number of impostor matches as assessed by a fingerprint recognizer. Experiments convey the efficacy of the proposed method in generating DeepMasterPrints. The underlying method is likely to have broad applications in fingerprint security as well as fingerprint synthesis.
Why are Big Data Matrices Approximately Low Rank?
Venue: arXiv cs.LG 2018
Year: 2018

Matrices of (approximate) low rank are pervasive in data science, appearing in recommender systems, movie preferences, topic models, medical records, and genomics. While there is a vast literature on how to exploit low rank structure in these datasets, there is less attention on explaining why the low rank structure appears in the first place. Here, we explain the effectiveness of low rank models in data science by considering a simple generative model for these matrices: we suppose that each row or column is associated to a (possibly high dimensional) bounded latent variable, and entries of the matrix are generated by applying a piecewise analytic function to these latent variables. These matrices are in general full rank. However, we show that we can approximate every entry of an $m \times n$ matrix drawn from this model to within a fixed absolute error by a low rank matrix whose rank grows as $\mathcal O(\log(m + n))$. Hence any sufficiently large matrix from such a latent variable model can be approximated, up to a small entrywise error, by a low rank matrix.
Patchnet: Interpretable Neural Networks for Image Classification
Venue: arXiv cs.CV 2018
Year: 2018

Understanding how a complex machine learning model makes a classification decision is essential for its acceptance in sensitive areas such as health care. Towards this end, we present PatchNet, a method that provides the features indicative of each class in an image using a tradeoff between restricting global image context and classification error. We mathematically analyze this tradeoff, demonstrate Patchnet's ability to construct sharp visual heatmap representations of the learned features, and quantitatively compare these features with features selected by domain experts by applying PatchNet to the classification of benign/malignant skin lesions from the ISBI-ISIC 2017 melanoma classification challenge.
On winning shifts of marked uniform substitutions
Venue: arXiv cs.FL 2018
Year: 2018

The second author introduced with I. Törmä a two-player word-building game [Playing with Subshifts, Fund. Inform. 132 (2014), 131--152]. The game has a predetermined (possibly finite) choice sequence $α_1$, $α_2$, $\ldots$ of integers such that on round $n$ the player $A$ chooses a subset $S_n$ of size $α_n$ of some fixed finite alphabet and the player $B$ picks a letter from the set $S_n$. The outcome is determined by whether the word obtained by concatenating the letters $B$ picked lies in a prescribed target set $X$ (a win for player $A$) or not (a win for player $B$). Typically, we consider $X$ to be a subshift. The winning shift $W(X)$ of a subshift $X$ is defined as the set of choice sequences for which $A$ has a winning strategy when the target set is the language of $X$. The winning shift $W(X)$ mirrors some properties of $X$. For instance, $W(X)$ and $X$ have the same entropy. Virtually nothing is known about the structure of the winning shifts of subshifts common in combinatorics on words. In this paper, we study the winning shifts of subshifts generated by marked uniform substitutions, and show that these winning shifts, viewed as subshifts, also have a substitutive structure. Particularly, we give an explicit description of the winning shift for the generalized Thue-Morse substitutions. It is known that $W(X)$ and $X$ have the same factor complexity. As an example application, we exploit this connection to give a simple derivation of the first difference and factor complexity functions of subshifts generated by marked substitutions. We describe these functions in particular detail for the generalized Thue-Morse substitutions.