OpenRaiser/Intern-Atlas huggingface dataset:
Multi-user Multi-task Offloading and Resource Allocation in Mobile Cloud Systems
Venue: arXiv cs.IT 2018
Year: 2018

We consider a general multi-user Mobile Cloud Computing (MCC) system where each mobile user has multiple independent tasks. These mobile users share the computation and communication resources while offloading tasks to the cloud. We study both the conventional MCC where tasks are offloaded to the cloud through a wireless access point, and MCC with a computing access point (CAP), where the CAP serves both as the network access gateway and a computation service provider to the mobile users. We aim to jointly optimize the offloading decisions of all users as well as the allocation of computation and communication resources, to minimize the overall cost of energy, computation, and delay for all users. The optimization problem is formulated as a non-convex quadratically constrained quadratic program, which is NP-hard in general. For the case without a CAP, an efficient approximate solution named MUMTO is proposed by using separable semidefinite relaxation (SDR), followed by recovery of the binary offloading decision and optimal allocation of the communication resource. To solve the more complicated problem with a CAP, we further propose an efficient three-step algorithm named MUMTO-C comprising of generalized MUMTO SDR with CAP, alternating optimization, and sequential tuning, which always computes a locally optimal solution. For performance benchmarking, we further present numerical lower bounds of the minimum system cost with and without the CAP. By comparison with this lower bound, our simulation results show that the proposed solutions for both scenarios give nearly optimal performance under various parameter settings, and the resultant efficient utilization of a CAP can bring substantial cost benefit.
Comparative Study of Approximate Multipliers
Venue: arXiv cs.ET 2018
Year: 2018

Approximate multipliers are widely being advocated for energy-efficient computing in applications that exhibit an inherent tolerance to inaccuracy. However, the inclusion of accuracy as a key design parameter, besides the performance, area and power, makes the identification of the most suitable approximate multiplier quite challenging. In this paper, we identify three major decision making factors for the selection of an approximate multipliers circuit: (1) the type of approximate full adder (FA) used to construct the multiplier, (2) the architecture, i.e., array or tree, of the multiplier and (3) the placement of sub-modules of approximate and exact multipliers in the main multiplier module. Based on these factors, we explored the design space for circuit level implementations of approximate multipliers. We used circuit level implementations of some of the most widely used approximate full adders, i.e., approximate mirror adders, XOR/XNOR based approximate full adders and Inexact adder cell. These FA cells are then used to develop circuits for the approximate high order compressors as building blocks for 8x8 array and tree multipliers. We then develop various implementations of higher bit multipliers by using a combination of exact and inaccurate 8x8 multiplier cells. All these implementations have been done using the Cadence's Spectre tool with the TSMC65nm technology. The design space of these multipliers is explored based on their power, area, delay and error and the best approximate multiplier designs are identified. The report also presents the validation of our results using an image blending application. An open source library of implemented cells and multiplier circuits are available online.
Efficient and accurate inversion of multiple scattering with deep learning
Venue: arXiv cs.CV 2018
Year: 2018

Image reconstruction under multiple light scattering is crucial in a number of applications such as diffraction tomography. The reconstruction problem is often formulated as a nonconvex optimization, where a nonlinear measurement model is used to account for multiple scattering and regularization is used to enforce prior constraints on the object. In this paper, we propose a powerful alternative to this optimization-based view of image reconstruction by designing and training a deep convolutional neural network that can invert multiple scattered measurements to produce a high-quality image of the refractive index. Our results on both simulated and experimental datasets show that the proposed approach is substantially faster and achieves higher imaging quality compared to the state-of-the-art methods based on optimization.
ShIFT: A Semi-haptic Interface for Flute Tutoring
Venue: arXiv cs.HC 2018
Year: 2018

Traditional instrument learning is time-consuming. It begins with learning music notation and necessitates layers of sophistication and abstraction. Haptic interfaces open another door to the music world for the vast majority of beginners when traditional training methods are not effective. However, existing haptic interfaces can only deal with specially designed pieces with great restrictions on performance duration and pitch range due to the fact that not all performance motions could be guided haptically for most instruments. Our system breaks such restrictions using a semi-haptic interface. For the first time, the pitch range of the haptically learned pieces goes beyond an octave (with the fingering motion covers most of the possible choices) and the duration of learned pieces cover a whole phrase. This significant change leads to a more realistic instrument learning process. Experiments show that our semi-haptic interface is effective as long as learners are not "tone deaf." Using our prototype device, the learning rate is about 30% faster compared to learning from videos.
Ratio-Preserving Half-Cylindrical Warps for Natural Image Stitching
Venue: arXiv cs.CV 2018
Year: 2018

A novel warp for natural image stitching is proposed that utilizes the property of cylindrical warp and a horizontal pixel selection strategy. The proposed ratio-preserving half-cylindrical warp is a combination of homography and cylindrical warps which guarantees alignment by homography and possesses less projective distortion by cylindrical warp. Unlike previous approaches applying cylindrical warp before homography, we use partition lines to divide the image into different parts and apply homography in the overlapping region while a composition of homography and cylindrical warps in the non-overlapping region. The pixel selection strategy then samples the points in horizontal and reconstructs the image via interpolation to further reduce horizontal distortion by maintaining the ratio as similarity. With applying half-cylindrical warp and horizontal pixel selection, the projective distortion in vertical and horizontal is mitigated simultaneously. Experiments show that our warp is efficient and produces a more natural-looking stitched result than previous methods.
White matter hyperintensity segmentation from T1 and FLAIR images using fully convolutional neural networks enhanced with residual connections
Venue: arXiv cs.CV 2018
Year: 2018

Segmentation and quantification of white matter hyperintensities (WMHs) are of great importance in studying and understanding various neurological and geriatric disorders. Although automatic methods have been proposed for WMH segmentation on magnetic resonance imaging (MRI), manual corrections are often necessary to achieve clinically practical results. Major challenges for WMH segmentation stem from their inhomogeneous MRI intensities, random location and size distributions, and MRI noise. The presence of other brain anatomies or diseases with enhanced intensities adds further difficulties. To cope with these challenges, we present a specifically designed fully convolutional neural network (FCN) with residual connections to segment WMHs by using combined T1 and fluid-attenuated inversion recovery (FLAIR) images. Our customized FCN is designed to be straightforward and generalizable, providing efficient end-to-end training due to its enhanced information propagation. We tested our method on the open WMH Segmentation Challenge MICCAI2017 dataset, and, despite our method's relative simplicity, results show that it performs amongst the leading techniques across five metrics. More importantly, our method achieves the best score for hausdorff distance and average volume difference in testing datasets from two MRI scanners that were not included in training, demonstrating better generalization ability of our proposed method over its competitors.
Swapping Colored Tokens on Graphs
Venue: arXiv cs.DS 2018
Year: 2018

We investigate the computational complexity of the following problem. We are given a graph in which each vertex has an initial and a target color. Each pair of adjacent vertices can swap their current colors. Our goal is to perform the minimum number of swaps so that the current and target colors agree at each vertex. When the colors are chosen from {1,2,...,c}, we call this problem c-Colored Token Swapping since the current color of a vertex can be seen as a colored token placed on the vertex. We show that c-Colored Token Swapping is NP-complete for c = 3 even if input graphs are restricted to connected planar bipartite graphs of maximum degree 3. We then show that 2-Colored Token Swapping can be solved in polynomial time for general graphs and in linear time for trees. Besides, we show that, the problem for complete graphs is fixed-parameter tractable when parameterized by the number of colors, while it is known to be NP-complete when the number of colors is unbounded.
An improved isomorphism test for bounded-tree-width graphs
Venue: arXiv cs.DS 2018
Year: 2018

We give a new fpt algorithm testing isomorphism of $n$-vertex graphs of tree width $k$ in time $2^{k\operatorname{polylog} (k)}\operatorname{poly} (n)$, improving the fpt algorithm due to Lokshtanov, Pilipczuk, Pilipczuk, and Saurabh (FOCS 2014), which runs in time $2^{\mathcal{O}(k^5\log k)}\operatorname{poly} (n)$. Based on an improved version of the isomorphism-invariant graph decomposition technique introduced by Lokshtanov et al., we prove restrictions on the structure of the automorphism groups of graphs of tree width $k$. Our algorithm then makes heavy use of the group theoretic techniques introduced by Luks (JCSS 1982) in his isomorphism test for bounded degree graphs and Babai (STOC 2016) in his quasipolynomial isomorphism test. In fact, we even use Babai's algorithm as a black box in one place. We also give a second algorithm which, at the price of a slightly worse running time $2^{\mathcal{O}(k^2 \log k)}\operatorname{poly} (n)$, avoids the use of Babai's algorithm and, more importantly, has the additional benefit that it can also used as a canonization algorithm.
TBD: Benchmarking and Analyzing Deep Neural Network Training
Venue: arXiv cs.LG 2018
Year: 2018

The recent popularity of deep neural networks (DNNs) has generated a lot of research interest in performing DNN-related computation efficiently. However, the primary focus is usually very narrow and limited to (i) inference -- i.e. how to efficiently execute already trained models and (ii) image classification networks as the primary benchmark for evaluation. Our primary goal in this work is to break this myopic view by (i) proposing a new benchmark for DNN training, called TBD (TBD is short for Training Benchmark for DNNs), that uses a representative set of DNN models that cover a wide range of machine learning applications: image classification, machine translation, speech recognition, object detection, adversarial networks, reinforcement learning, and (ii) by performing an extensive performance analysis of training these different applications on three major deep learning frameworks (TensorFlow, MXNet, CNTK) across different hardware configurations (single-GPU, multi-GPU, and multi-machine). TBD currently covers six major application domains and eight different state-of-the-art models. We present a new toolchain for performance analysis for these models that combines the targeted usage of existing performance analysis tools, careful selection of new and existing metrics and methodologies to analyze the results, and utilization of domain specific characteristics of DNN training. We also build a new set of tools for memory profiling in all three major frameworks; much needed tools that can finally shed some light on precisely how much memory is consumed by different data structures (weights, activations, gradients, workspace) in DNN training. By using our tools and methodologies, we make several important observations and recommendations on where the future research and optimization of DNN training should be focused.
Table Based Detection of Degenerate Predicates in Free Space Construction
Venue: arXiv cs.CG 2018
Year: 2018

The key to a robust and efficient implementation of a computational geometry algorithm is an efficient algorithm for detecting degenerate predicates. We study degeneracy detection in constructing the free space of a polyhedron that rotates around a fixed axis and translates freely relative to another polyhedron. The structure of the free space is determined by the signs of univariate polynomials, called angle polynomials, whose coefficients are polynomials in the coordinates of the vertices of the polyhedra. Every predicate is expressible as the sign of an angle polynomial $f$ evaluated at a zero $t$ of an angle polynomial $g$. A predicate is degenerate (the sign is zero) when $t$ is a zero of a common factor of $f$ and $g$. We present an efficient degeneracy detection algorithm based on a one-time factoring of every possible angle polynomial. Our algorithm is 3500 times faster than the standard algorithm based on greatest common divisor computation. It reduces the share of degeneracy detection in our free space computations from 90% to 0.5% of the running time.
Inverse Visual Question Answering: A New Benchmark and VQA Diagnosis Tool
Venue: arXiv cs.CV 2018
Year: 2018

In recent years, visual question answering (VQA) has become topical. The premise of VQA's significance as a benchmark in AI, is that both the image and textual question need to be well understood and mutually grounded in order to infer the correct answer. However, current VQA models perhaps `understand' less than initially hoped, and instead master the easier task of exploiting cues given away in the question and biases in the answer distribution. In this paper we propose the inverse problem of VQA (iVQA). The iVQA task is to generate a question that corresponds to a given image and answer pair. We propose a variational iVQA model that can generate diverse, grammatically correct and content correlated questions that match the given answer. Based on this model, we show that iVQA is an interesting benchmark for visuo-linguistic understanding, and a more challenging alternative to VQA because an iVQA model needs to understand the image better to be successful. As a second contribution, we show how to use iVQA in a novel reinforcement learning framework to diagnose any existing VQA model by way of exposing its belief set: the set of question-answer pairs that the VQA model would predict true for a given image. This provides a completely new window into what VQA models `believe' about images. We show that existing VQA models have more erroneous beliefs than previously thought, revealing their intrinsic weaknesses. Suggestions are then made on how to address these weaknesses going forward.
A promise checked is a promise kept: Inspection Testing
Venue: arXiv cs.PL 2018
Year: 2018

Occasionally, developers need to ensure that the compiler treats their code in a specific way that is only visible by inspecting intermediate or final compilation artifacts. This is particularly common with carefully crafted compositional libraries, where certain usage patterns are expected to trigger an intricate sequence of compiler optimizations -- stream fusion is a well-known example. The developer of such a library has to manually inspect build artifacts and check for the expected properties. Because this is too tedious to do often, it will likely go unnoticed if the property is broken by a change to the library code, its dependencies or the compiler. The lack of automation has led to released versions of such libraries breaking their documented promises. This indicates that there is an unrecognized need for a new testing paradigm, inspection testing, where the programmer declaratively describes non-functional properties of an compilation artifact and the compiler checks these properties. We define inspection testing abstractly, implement it in the context of Haskell and show that it increases the quality of such libraries.
Dynamic Natural Language Processing with Recurrence Quantification Analysis
Venue: arXiv cs.CL 2018
Year: 2018

Writing and reading are dynamic processes. As an author composes a text, a sequence of words is produced. This sequence is one that, the author hopes, causes a revisitation of certain thoughts and ideas in others. These processes of composition and revisitation by readers are ordered in time. This means that text itself can be investigated under the lens of dynamical systems. A common technique for analyzing the behavior of dynamical systems, known as recurrence quantification analysis (RQA), can be used as a method for analyzing sequential structure of text. RQA treats text as a sequential measurement, much like a time series, and can thus be seen as a kind of dynamic natural language processing (NLP). The extension has several benefits. Because it is part of a suite of time series analysis tools, many measures can be extracted in one common framework. Secondly, the measures have a close relationship with some commonly used measures from natural language processing. Finally, using recurrence analysis offers an opportunity expand analysis of text by developing theoretical descriptions derived from complex dynamic systems. We showcase an example analysis on 8,000 texts from the Gutenberg Project, compare it to well-known NLP approaches, and describe an R package (crqanlp) that can be used in conjunction with R library crqa.
Mechanisms for producing a working knowledge: Enacting, orchestrating and organizing
Venue: arXiv cs.CY 2018
Year: 2018

Given that knowledge (intensive) work takes place immersed in truly heterogenous networks of knowledge representations (codified, narrative, embedded in routines, inscribed in artefacts), our analysis is geared towards how the transformation of these resources are enacted in the practise of everyday, knowledge work. First, we discuss the work, strategies and mechanisms implied in rendering knowledge as credible, trustworthy and relevant. Second, we analyse how sediments of historically superimposed layers of knowledge representations need to be enacted through selective repetitions, omittance and highlighting to preserve it as living knowledge. Third, supplementing the more cognitivelly oriented aspects of knowledge work, we discuss how codified knowledge representations organise, coordinate and delegate work. Empirically, we study clinical work in large hospitals, a type of work, we argue, that unduely has been left out of traditional listings of knowledge work
Diagnostic Classification Of Lung Nodules Using 3D Neural Networks
Venue: arXiv cs.CV 2018
Year: 2018

Lung cancer is the leading cause of cancer-related death worldwide. Early diagnosis of pulmonary nodules in Computed Tomography (CT) chest scans provides an opportunity for designing effective treatment and making financial and care plans. In this paper, we consider the problem of diagnostic classification between benign and malignant lung nodules in CT images, which aims to learn a direct mapping from 3D images to class labels. To achieve this goal, four two-pathway Convolutional Neural Networks (CNN) are proposed, including a basic 3D CNN, a novel multi-output network, a 3D DenseNet, and an augmented 3D DenseNet with multi-outputs. These four networks are evaluated on the public LIDC-IDRI dataset and outperform most existing methods. In particular, the 3D multi-output DenseNet (MoDenseNet) achieves the state-of-the-art classification accuracy on the task of end-to-end lung nodule diagnosis. In addition, the networks pretrained on the LIDC-IDRI dataset can be further extended to handle smaller datasets using transfer learning. This is demonstrated on our dataset with encouraging prediction accuracy in lung nodule classification.
Twelve Simple Algorithms to Compute Fibonacci Numbers
Venue: arXiv cs.DS 2018
Year: 2018

The Fibonacci numbers are a sequence of integers in which every number after the first two, 0 and 1, is the sum of the two preceding numbers. These numbers are well known and algorithms to compute them are so easy that they are often used in introductory algorithms courses. In this paper, we present twelve of these well-known algorithms and some of their properties. These algorithms, though very simple, illustrate multiple concepts from the algorithms field, so we highlight them. We also present the results of a small-scale experimental comparison of their runtimes on a personal laptop. Finally, we provide a list of homework questions for the students. We hope that this paper can serve as a useful resource for the students learning the basics of algorithms.
Real-time Burst Photo Selection Using a Light-Head Adversarial Network
Venue: arXiv cs.CV 2018
Year: 2018

We present an automatic moment capture system that runs in real-time on mobile cameras. The system is designed to run in the viewfinder mode and capture a burst sequence of frames before and after the shutter is pressed. For each frame, the system predicts in real-time a "goodness" score, based on which the best moment in the burst can be selected immediately after the shutter is released, without any user interference. To solve the problem, we develop a highly efficient deep neural network ranking model, which implicitly learns a "latent relative attribute" space to capture subtle visual differences within a sequence of burst images. Then the overall goodness is computed as a linear aggregation of the goodnesses of all the latent attributes. The latent relative attributes and the aggregation function can be seamlessly integrated in one fully convolutional network and trained in an end-to-end fashion. To obtain a compact model which can run on mobile devices in real-time, we have explored and evaluated a wide range of network design choices, taking into account the constraints of model size, computational cost, and accuracy. Extensive studies show that the best frame predicted by our model hit users' top-1 (out of 11 on average) choice for $64.1\%$ cases and top-3 choices for $86.2\%$ cases. Moreover, the model(only 0.47M Bytes) can run in real time on mobile devices, e.g. only 13ms on iPhone 7 for one frame prediction.