OpenRaiser/Intern-Atlas huggingface dataset:
Exploitation of Stragglers in Coded Computation
Venue: arXiv cs.IT 2018
Year: 2018

In cloud computing systems slow processing nodes, often referred to as "stragglers", can significantly extend the computation time. Recent results have shown that error correction coding can be used to reduce the effect of stragglers. In this work we introduce a scheme that, in addition to using error correction to distribute mixed jobs across nodes, is also able to exploit the work completed by all nodes, including stragglers. We first consider vector-matrix multiplication and apply maximum distance separable (MDS) codes to small blocks of sub-matrices. The worker nodes process blocks sequentially, working block-by-block, transmitting partial per-block results to the master as they are completed. Sub-blocking allows a more continuous completion process, which thereby allows us to exploit the work of a much broader spectrum of processors and reduces computation time. We then apply this technique to matrix-matrix multiplication using product code. In this case, we show that the order of computing sub-tasks is a new degree of design freedom that can be exploited to reduce computation time further. We propose a novel approach to analyze the finishing time, which is different from typical order statistics. Simulation results show that the expected computation time decreases by a factor of at least two in compared to previous methods.
DeepObfuscation: Securing the Structure of Convolutional Neural Networks via Knowledge Distillation
Venue: arXiv cs.CR 2018
Year: 2018

This paper investigates the piracy problem of deep learning models. Designing and training a well-performing model is generally expensive. However, when releasing them, attackers may reverse engineer the models and pirate their design. This paper, therefore, proposes deep learning obfuscation, aiming at obstructing attackers from pirating a deep learning model. In particular, we focus on obfuscating convolutional neural networks (CNN), a widely employed type of deep learning architectures for image recognition. Our approach obfuscates a CNN model eventually by simulating its feature extractor with a shallow and sequential convolutional block. To this end, we employ a recursive simulation method and a joint training method to train the simulation network. The joint training method leverages both the intermediate knowledge generated by a feature extractor and data labels to train a simulation network. In this way, we can obtain an obfuscated model without accuracy loss. We have verified the feasibility of our approach with three prevalent CNNs, i.e., GoogLeNet, ResNet, and DenseNet. Although these networks are very deep with tens or hundreds of layers, we can simulate them in a shallow network including only five or seven convolutional layers. The obfuscated models are even more efficient than the original models. Our obfuscation approach is very effective to protect the critical structure of a deep learning model from being exposed to attackers. Moreover, it can also thwart attackers from pirating the model with transfer learning or incremental learning techniques because the shallow simulation network bears poor learning ability. To our best knowledge, this paper serves as a first attempt to obfuscate deep learning models, which may shed light on more future studies.
MONAS: Multi-Objective Neural Architecture Search using Reinforcement Learning
Venue: arXiv cs.LG 2018
Year: 2018

Recent studies on neural architecture search have shown that automatically designed neural networks perform as good as expert-crafted architectures. While most existing works aim at finding architectures that optimize the prediction accuracy, these architectures may have complexity and is therefore not suitable being deployed on certain computing environment (e.g., with limited power budgets). We propose MONAS, a framework for Multi-Objective Neural Architectural Search that employs reward functions considering both prediction accuracy and other important objectives (e.g., power consumption) when searching for neural network architectures. Experimental results showed that, compared to the state-ofthe-arts, models found by MONAS achieve comparable or better classification accuracy on computer vision applications, while satisfying the additional objectives such as peak power.
Customizing an Adversarial Example Generator with Class-Conditional GANs
Venue: arXiv cs.CV 2018
Year: 2018

Adversarial examples are intentionally crafted data with the purpose of deceiving neural networks into misclassification. When we talk about strategies to create such examples, we usually refer to perturbation-based methods that fabricate adversarial examples by applying invisible perturbations onto normal data. The resulting data reserve their visual appearance to human observers, yet can be totally unrecognizable to DNN models, which in turn leads to completely misleading predictions. In this paper, however, we consider crafting adversarial examples from existing data as a limitation to example diversity. We propose a non-perturbation-based framework that generates native adversarial examples from class-conditional generative adversarial networks.As such, the generated data will not resemble any existing data and thus expand example diversity, raising the difficulty in adversarial defense. We then extend this framework to pre-trained conditional GANs, in which we turn an existing generator into an "adversarial-example generator". We conduct experiments on our approach for MNIST and CIFAR10 datasets and have satisfactory results, showing that this approach can be a potential alternative to previous attack strategies.
Dynamic Trees with Almost-Optimal Access Cost
Venue: arXiv cs.DS 2018
Year: 2018

An optimal binary search tree for an access sequence on elements is a static tree that minimizes the total search cost. Constructing perfectly optimal binary search trees is expensive so the most efficient algorithms construct almost optimal search trees. There exists a long literature of constructing almost optimal search trees dynamically, i.e., when the access pattern is not known in advance. All of these trees, e.g., splay trees and treaps, provide a multiplicative approximation to the optimal search cost. In this paper we show how to maintain an almost optimal weighted binary search tree under access operations and insertions of new elements where the approximation is an additive constant. More technically, we maintain a tree in which the depth of the leaf holding an element $e_i$ does not exceed $\min(\log(W/w_i),\log n)+O(1)$ where $w_i$ is the number of times $e_i$ was accessed and $W$ is the total length of the access sequence. Our techniques can also be used to encode a sequence of $m$ symbols with a dynamic alphabetic code in $O(m)$ time so that the encoding length is bounded by $m(H+O(1))$, where $H$ is the entropy of the sequence. This is the first efficient algorithm for adaptive alphabetic coding that runs in constant time per symbol.
Belief Propagation List Decoding of Polar Codes
Venue: arXiv cs.IT 2018
Year: 2018

We propose a belief propagation list (BPL) decoder with comparable performance to the successive cancellation list (SCL) decoder of polar codes, which already achieves the maximum likelihood (ML) bound of polar codes for sufficiently large list size $L$. The proposed decoder is composed of multiple parallel independent belief propagation (BP) decoders based on differently permuted polar code factor graphs. A list of possible transmitted codewords is generated and the one closest to the received vector, in terms of Euclidean distance, is picked. To the best of our knowledge, the proposed BPL decoder provides the best performance of plain polar codes under iterative decoding known so far. The proposed algorithm does not require any changes in the polar code structure itself, rendering the BPL into an alternative to the SCL decoder, equipped with a soft output capability enabling, e.g., iterative detection and decoding to further improve performance. Further benefits are lower decoding latency compared to the SCL decoder and the possibility of high throughput implementations. Additionally, we show that a different selection strategy of frozen bit positions can further enhance the error-rate performance of the proposed decoder.
Reliable Wireless Multi-Hop Networks with Decentralized Slot Management: An Analysis of IEEE 802.15.4 DSME
Venue: arXiv cs.NI 2018
Year: 2018

Wireless communication is a key element in the realization of the Industrial Internet of Things for flexible and cost-efficient monitoring and control of industrial processes. Wireless mesh networks using IEEE 802.15.4 have a high potential for executing monitoring and control tasks with low energy consumption and low costs for deployment and maintenance. However, conventional medium access techniques based on carrier sensing cannot provide the required reliability for industrial applications. Therefore, the standard was extended with techniques for time-slotted medium access on multiple channels. In this paper, we present openDSME, a comprehensive implementation of the Deterministic and Synchronous Multi-channel Extension (DSME) and propose a method for traffic-aware and decentralized slot scheduling to enable scalable wireless industrial networks. The performance of DSME and our implementation is demonstrated in the OMNeT++ simulator and on a physically deployed wireless network in the FIT/IoT-LAB. It is shown that in the given scenarios, twice as much traffic can be delivered reliably by using DSME instead of CSMA/CA and that the energy consumption can be reduced significantly. The paper is completed by presenting important trade-offs for parameter selection and by uncovering open issues of the current specification that call for further effort in research and standardization.
Modeling Majorness as a Perceptual Property in Music from Listener Ratings
Venue: arXiv cs.SD 2018
Year: 2018

For the tasks of automatic music emotion recognition, genre recognition, music recommendation it is helpful to be able to extract mode from any section of a musical piece as a perceived amount of major or minor mode (majorness) inside that section, perceived as a whole (one or several melodies and any harmony present). In this paper we take a data-driven approach (modeling directly from data without giving an explicit definition or explicitly programming an algorithm) towards modeling this property. We collect annotations from musicians and show that majorness can be understood by musicians in an intuitive way. We model this property from the data using deep learning.
Dynamic texture analysis with diffusion in networks
Venue: arXiv cs.CV 2018
Year: 2018

Dynamic texture is a field of research that has gained considerable interest from computer vision community due to the explosive growth of multimedia databases. In addition, dynamic texture is present in a wide range of videos, which makes it very important in expert systems based on videos such as medical systems, traffic monitoring systems, forest fire detection system, among others. In this paper, a new method for dynamic texture characterization based on diffusion in directed networks is proposed. The dynamic texture is modeled as a directed network. The method consists in the analysis of the dynamic of this network after a series of graph cut transformations based on the edge weights. For each network transformation, the activity for each vertex is estimated. The activity is the relative frequency that one vertex is visited by random walks in balance. Then, texture descriptor is constructed by concatenating the activity histograms. The main contributions of this paper are the use of directed network modeling and diffusion in network to dynamic texture characterization. These tend to provide better performance in dynamic textures classification. Experiments with rotation and interference of the motion pattern were conducted in order to demonstrate the robustness of the method. The proposed approach is compared to other dynamic texture methods on two very well know dynamic texture database and on traffic condition classification, and outperform in most of the cases.
A comparative study of artificial intelligence and human doctors for the purpose of triage and diagnosis
Venue: arXiv cs.AI 2018
Year: 2018

Online symptom checkers have significant potential to improve patient care, however their reliability and accuracy remain variable. We hypothesised that an artificial intelligence (AI) powered triage and diagnostic system would compare favourably with human doctors with respect to triage and diagnostic accuracy. We performed a prospective validation study of the accuracy and safety of an AI powered triage and diagnostic system. Identical cases were evaluated by both an AI system and human doctors. Differential diagnoses and triage outcomes were evaluated by an independent judge, who was blinded from knowing the source (AI system or human doctor) of the outcomes. Independently of these cases, vignettes from publicly available resources were also assessed to provide a benchmark to previous studies and the diagnostic component of the MRCGP exam. Overall we found that the Babylon AI powered Triage and Diagnostic System was able to identify the condition modelled by a clinical vignette with accuracy comparable to human doctors (in terms of precision and recall). In addition, we found that the triage advice recommended by the AI System was, on average, safer than that of human doctors, when compared to the ranges of acceptable triage provided by independent expert judges, with only a minimal reduction in appropriateness.
Dynamic traffic resources allocation under elastic demand of users with space-time prism constraints
Venue: arXiv cs.GT 2018
Year: 2018

We present a conceptual framework for the dynamic traffic resources allocation problem in a situation of elastic demand among customers. We introduce an activity-based model to express customers' successive actions and transfers in order to capture the essential aspect of transfers as a derived demand. We focus on the decision-making of customers, in that they only use a mobility service when their space-time prism constraints represent the worst case. Under the setting with such elastic demand, we characterize a class of dynamic traffic resources allocation mechanisms that strictly keep space-time prism constraints of users and capacity constraints of traffic resources. Within the class of mechanisms, we show the optimal mechanism that maximizes discounted social welfare and show an exact solution algorithm for both, myopic and non-myopic settings, using the zero-suppressed binary decision diagram. We also present approximation algorithms that are still included in the class of mechanisms. In numerical studies, we showed that our proposed algorithm works effectively in settings with high rejection rates, meaning that this algorithm can be used to focus on the behavior of latent customers who have not used mobility services so far. The proposed non-myopic algorithm is suitable to design services for limited small number of customers, for example a car-sharing services for prescribed members, while the proposed myopic algorithm is suitable for designing services for a large unspecified number of customers, for example, a ride-sharing service in a large city.
Decremental SPQR-trees for Planar Graphs
Venue: arXiv cs.DS 2018
Year: 2018

We present a decremental data structure for maintaining the SPQR-tree of a planar graph subject to edge contractions and deletions. The update time, amortized over $Ω(n)$ operations, is $O(\log^2 n)$. Via SPQR-trees, we give a decremental data structure for maintaining $3$-vertex connectivity in planar graphs. It answers queries in $O(1)$ time and processes edge deletions and contractions in $O(\log^2 n)$ amortized time. This is an exponential improvement over the previous best bound of $O(\sqrt{n}\,)$ that has stood for over 20 years. In addition, the previous data structures only supported edge deletions.
Accurate and efficient video de-fencing using convolutional neural networks and temporal information
Venue: arXiv cs.CV 2018
Year: 2018

De-fencing is to eliminate the captured fence on an image or a video, providing a clear view of the scene. It has been applied for many purposes including assisting photographers and improving the performance of computer vision algorithms such as object detection and recognition. However, the state-of-the-art de-fencing methods have limited performance caused by the difficulty of fence segmentation and also suffer from the motion of the camera or objects. To overcome these problems, we propose a novel method consisting of segmentation using convolutional neural networks and a fast/robust recovery algorithm. The segmentation algorithm using convolutional neural network achieves significant improvement in the accuracy of fence segmentation. The recovery algorithm using optical flow produces plausible de-fenced images and videos. The proposed method is experimented on both our diverse and complex dataset and publicly available datasets. The experimental results demonstrate that the proposed method achieves the state-of-the-art performance for both segmentation and content recovery.
How To Extract Fashion Trends From Social Media? A Robust Object Detector With Support For Unsupervised Learning
Venue: arXiv cs.CV 2018
Year: 2018

With the proliferation of social media, fashion inspired from celebrities, reputed designers as well as fashion influencers has shortened the cycle of fashion design and manufacturing. However, with the explosion of fashion related content and large number of user generated fashion photos, it is an arduous task for fashion designers to wade through social media photos and create a digest of trending fashion. This necessitates deep parsing of fashion photos on social media to localize and classify multiple fashion items from a given fashion photo. While object detection competitions such as MSCOCO have thousands of samples for each of the object categories, it is quite difficult to get large labeled datasets for fast fashion items. Moreover, state-of-the-art object detectors do not have any functionality to ingest large amount of unlabeled data available on social media in order to fine tune object detectors with labeled datasets. In this work, we show application of a generic object detector, that can be pretrained in an unsupervised manner, on 24 categories from recently released Open Images V4 dataset. We first train the base architecture of the object detector using unsupervisd learning on 60K unlabeled photos from 24 categories gathered from social media, and then subsequently fine tune it on 8.2K labeled photos from Open Images V4 dataset. On 300 X 300 image inputs, we achieve 72.7% mAP on a test dataset of 2.4K photos while performing 11% to 17% better as compared to the state-of-the-art object detectors. We show that this improvement is due to our choice of architecture that lets us do unsupervised learning and that performs significantly better in identifying small objects.
Deep Learning-Aided Projected Gradient Detector for Massive Overloaded MIMO Channels
Venue: arXiv cs.IT 2018
Year: 2018

The paper presents a deep learning-aided iterative detection algorithm for massive overloaded MIMO systems. Since the proposed algorithm is based on the projected gradient descent method with trainable parameters, it is named as trainable projected descent-detector (TPG-detector). The trainable internal parameters can be optimized with standard deep learning techniques such as back propagation and stochastic gradient descent algorithms. This approach referred to as data-driven tuning brings notable advantages of the proposed scheme such as fast convergence. The numerical experiments show that TPG-detector achieves comparable detection performance to those of the known algorithms for massive overloaded MIMO channels with lower computation cost.
Beyond Precision: A Study on Recall of Initial Retrieval with Neural Representations
Venue: arXiv cs.IR 2018
Year: 2018

Vocabulary mismatch is a central problem in information retrieval (IR), i.e., the relevant documents may not contain the same (symbolic) terms of the query. Recently, neural representations have shown great success in capturing semantic relatedness, leading to new possibilities to alleviate the vocabulary mismatch problem in IR. However, most existing efforts in this direction have been devoted to the re-ranking stage. That is to leverage neural representations to help re-rank a set of candidate documents, which are typically obtained from an initial retrieval stage based on some symbolic index and search scheme (e.g., BM25 over the inverted index). This naturally raises a question: if the relevant documents have not been found in the initial retrieval stage due to vocabulary mismatch, there would be no chance to re-rank them to the top positions later. Therefore, in this paper, we study the problem how to employ neural representations to improve the recall of relevant documents in the initial retrieval stage. Specifically, to meet the efficiency requirement of the initial stage, we introduce a neural index for the neural representations of documents, and propose two hybrid search schemes based on both neural and symbolic indices, namely the parallel search scheme and the sequential search scheme. Our experiments show that both hybrid index and search schemes can improve the recall of the initial retrieval stage with small overhead.
Efficient CNN Implementation for Eye-Gaze Estimation on Low-Power/Low-Quality Consumer Imaging Systems
Venue: arXiv cs.CV 2018
Year: 2018

Accurate and efficient eye gaze estimation is important for emerging consumer electronic systems such as driver monitoring systems and novel user interfaces. Such systems are required to operate reliably in difficult, unconstrained environments with low power consumption and at minimal cost. In this paper a new hardware friendly, convolutional neural network model with minimal computational requirements is introduced and assessed for efficient appearance-based gaze estimation. The model is tested and compared against existing appearance based CNN approaches, achieving better eye gaze accuracy with significantly fewer computational requirements. A brief updated literature review is also provided.
On Low-Complexity Decoding of Product Codes for High-Throughput Fiber-Optic Systems
Venue: arXiv cs.IT 2018
Year: 2018

We study low-complexity iterative decoding algorithms for product codes. We revisit two algorithms recently proposed by the authors based on bounded distance decoding (BDD) of the component codes that improve the performance of conventional iterative BDD (iBDD). We then propose a novel decoding algorithm that is based on generalized minimum distance decoding of the component codes. The proposed algorithm closes over 50% of the performance gap between iBDD and turbo product decoding (TPD) based on the Chase-Pyndiah algorithm. Moreover, the algorithm only leads to a limited increase in complexity with respect to iBDD and has significantly lower complexity than TPD. The studied algorithms are particularly interesting for high-throughput fiber-optic communications.
TheoryGuru: A Mathematica Package to apply Quantifier Elimination
Venue: arXiv cs.SC 2018
Year: 2018

We consider the use of Quantifier Elimination (QE) technology for automated reasoning in economics. There is a great body of work considering QE applications in science and engineering but we demonstrate here that it also has use in the social sciences. We explain how many suggested theorems in economics could either be proven, or even have their hypotheses shown to be inconsistent, automatically via QE. However, economists who this technology could benefit are usually unfamiliar with QE, and the use of mathematical software generally. This motivated the development of a Mathematica Package TheoryGuru, whose purpose is to lower the costs of applying QE to economics. We describe the package's functionality and give examples of its use.