OpenRaiser/Intern-Atlas huggingface dataset:
Fairly Allocating Contiguous Blocks of Indivisible Items
Venue: arXiv cs.GT 2018
Year: 2018

In this paper, we study the classic problem of fairly allocating indivisible items with the extra feature that the items lie on a line. Our goal is to find a fair allocation that is contiguous, meaning that the bundle of each agent forms a contiguous block on the line. While allocations satisfying the classical fairness notions of proportionality, envy-freeness, and equitability are not guaranteed to exist even without the contiguity requirement, we show the existence of contiguous allocations satisfying approximate versions of these notions that do not degrade as the number of agents or items increases. We also study the efficiency loss of contiguous allocations due to fairness constraints.
Reconstruction Error Bounds for Compressed Sensing under Poisson or Poisson-Gaussian Noise Using Variance Stabilization Transforms
Venue: arXiv cs.IT 2018
Year: 2018

Most existing bounds for signal reconstruction from compressive measurements make the assumption of additive signal-independent noise. However in many compressive imaging systems, the noise statistics are more accurately represented by Poisson or Poisson-Gaussian noise models. In this paper, we derive upper bounds for signal reconstruction error from compressive measurements which are corrupted by Poisson or Poisson-Gaussian noise. The features of our bounds are as follows: (1) The bounds are derived for a probabilistically motivated, computationally tractable convex estimator with principled parameter selection. The estimator penalizes signal sparsity subject to a constraint that imposes an upper bound on a term based on variance stabilization transforms to approximate the Poisson or Poisson-Gaussian negative log-likelihoods. (2) They are applicable to signals that are sparse as well as compressible in any orthonormal basis, and are derived for compressive systems obeying realistic constraints such as non-negativity and flux-preservation. We present extensive numerical results for signal reconstruction under varying number of measurements and varying signal intensity levels.
Improving Foot-Mounted Inertial Navigation Through Real-Time Motion Classification
Venue: arXiv cs.RO 2018
Year: 2018

We present a method to improve the accuracy of a foot-mounted, zero-velocity-aided inertial navigation system (INS) by varying estimator parameters based on a real-time classification of motion type. We train a support vector machine (SVM) classifier using inertial data recorded by a single foot-mounted sensor to differentiate between six motion types (walking, jogging, running, sprinting, crouch-walking, and ladder-climbing) and report mean test classification accuracy of over 90% on a dataset with five different subjects. From these motion types, we select two of the most common (walking and running), and describe a method to compute optimal zero-velocity detection parameters tailored to both a specific user and motion type by maximizing the detector F-score. By combining the motion classifier with a set of optimal detection parameters, we show how we can reduce INS position error during mixed walking and running motion. We evaluate our adaptive system on a total of 5.9 km of indoor pedestrian navigation performed by five different subjects moving along a 130 m path with surveyed ground truth markers.
Journal of Open Source Software (JOSS): design and first-year review
Venue: arXiv cs.DL 2018
Year: 2018

This article describes the motivation, design, and progress of the Journal of Open Source Software (JOSS). JOSS is a free and open-access journal that publishes articles describing research software. It has the dual goals of improving the quality of the software submitted and providing a mechanism for research software developers to receive credit. While designed to work within the current merit system of science, JOSS addresses the dearth of rewards for key contributions to science made in the form of software. JOSS publishes articles that encapsulate scholarship contained in the software itself, and its rigorous peer review targets the software components: functionality, documentation, tests, continuous integration, and the license. A JOSS article contains an abstract describing the purpose and functionality of the software, references, and a link to the software archive. The article is the entry point of a JOSS submission, which encompasses the full set of software artifacts. Submission and review proceed in the open, on GitHub. Editors, reviewers, and authors work collaboratively and openly. Unlike other journals, JOSS does not reject articles requiring major revision; while not yet accepted, articles remain visible and under review until the authors make adequate changes (or withdraw, if unable to meet requirements). Once an article is accepted, JOSS gives it a DOI, deposits its metadata in Crossref, and the article can begin collecting citations on indexers like Google Scholar and other services. Authors retain copyright of their JOSS article, releasing it under a Creative Commons Attribution 4.0 International License. In its first year, starting in May 2016, JOSS published 111 articles, with more than 40 additional articles under review. JOSS is a sponsored project of the nonprofit organization NumFOCUS and is an affiliate of the Open Source Initiative.
Functional approach to the error control in adaptive IgA schemes for elliptic boundary value problems
Venue: arXiv cs.NA 2018
Year: 2018

This work presents a numerical study of functional type a posteriori error estimates for IgA approximation schemes in the context of elliptic boundary-value problems. Along with the detailed discussion of the most crucial properties of such estimates, we present the algorithm of a reliable solution approximation together with the scheme of efficient a posteriori error bound generation-based on solving an auxiliary problem with respect to an introduced vector-valued variable. In this approach, we take advantage of B-(THB-)spline's high smoothness for the auxiliary vector function reconstruction, which, at the same time, allows to use much coarser meshes and decrease the number of unknowns substantially. The most representative numerical results, obtained during a systematic testing of error estimates, are presented in the second part of the paper. The efficiency of the obtained error bounds is analysed from both the error estimation (indication) and the computational expenses points of view. Several examples illustrate that functional error estimates (alternatively referred to as the majorants and minorants of deviation from an exact solution) perform a much sharper error control than, for instance, residual-based error estimates. Simultaneously, assembling and solving the routines for an auxiliary variable reconstruction which generate the majorant of an error can be executed several times faster than the routines for a primal unknown.
Round Compression for Parallel Matching Algorithms
Venue: arXiv cs.DS 2018
Year: 2018

For over a decade now we have been witnessing the success of {\em massive parallel computation} (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. One of the reasons for their success is the fact that these frameworks are able to accurately capture the nature of large-scale computation. In particular, compared to the classic distributed algorithms or PRAM models, these frameworks allow for much more local computation. The fundamental question that arises in this context is though: can we leverage this additional power to obtain even faster parallel algorithms? A prominent example here is the {\em maximum matching} problem---one of the most classic graph problems. It is well known that in the PRAM model one can compute a 2-approximate maximum matching in $O(\log{n})$ rounds. However, the exact complexity of this problem in the MPC framework is still far from understood. Lattanzi et al. showed that if each machine has $n^{1+Ω(1)}$ memory, this problem can also be solved $2$-approximately in a constant number of rounds. These techniques, as well as the approaches developed in the follow up work, seem though to get stuck in a fundamental way at roughly $O(\log{n})$ rounds once we enter the near-linear memory regime. It is thus entirely possible that in this regime, which captures in particular the case of sparse graph computations, the best MPC round complexity matches what one can already get in the PRAM model, without the need to take advantage of the extra local computation power. In this paper, we finally refute that perplexing possibility. That is, we break the above $O(\log n)$ round complexity bound even in the case of {\em slightly sublinear} memory per machine. In fact, our improvement here is {\em almost exponential}: we are able to deliver a $(2+ε)$-approximation to maximum matching, for any fixed constant $ε>0$, in $O((\log \log n)^2)$ rounds.
Deep Learning with Topological Signatures
Venue: arXiv cs.CV 2018
Year: 2018

Inferring topological and geometrical information from data can offer an alternative perspective on machine learning problems. Methods from topological data analysis, e.g., persistent homology, enable us to obtain such information, typically in the form of summary representations of topological features. However, such topological signatures often come with an unusual structure (e.g., multisets of intervals) that is highly impractical for most machine learning techniques. While many strategies have been proposed to map these topological signatures into machine learning compatible representations, they suffer from being agnostic to the target learning task. In contrast, we propose a technique that enables us to input topological signatures to deep neural networks and learn a task-optimal representation during training. Our approach is realized as a novel input layer with favorable theoretical properties. Classification experiments on 2D object shapes and social network graphs demonstrate the versatility of the approach and, in case of the latter, we even outperform the state-of-the-art by a large margin.
Automatic Recognition of Facial Displays of Unfelt Emotions
Venue: arXiv cs.CV 2018
Year: 2018

Humans modify their facial expressions in order to communicate their internal states and sometimes to mislead observers regarding their true emotional states. Evidence in experimental psychology shows that discriminative facial responses are short and subtle. This suggests that such behavior would be easier to distinguish when captured in high resolution at an increased frame rate. We are proposing SASE-FE, the first dataset of facial expressions that are either congruent or incongruent with underlying emotion states. We show that overall the problem of recognizing whether facial movements are expressions of authentic emotions or not can be successfully addressed by learning spatio-temporal representations of the data. For this purpose, we propose a method that aggregates features along fiducial trajectories in a deeply learnt space. Performance of the proposed model shows that on average it is easier to distinguish among genuine facial expressions of emotion than among unfelt facial expressions of emotion and that certain emotion pairs such as contempt and disgust are more difficult to distinguish than the rest. Furthermore, the proposed methodology improves state of the art results on CK+ and OULU-CASIA datasets for video emotion recognition, and achieves competitive results when classifying facial action units on BP4D datase.
A Tight Approximation for Co-flow Scheduling for Minimizing Total Weighted Completion Time
Venue: arXiv cs.DS 2018
Year: 2018

Co-flows model a modern scheduling setting that is commonly found in a variety of applications in distributed and cloud computing. In co-flow scheduling, there are $m$ input ports and $m$ output ports. Each co-flow $j \in J$ can be represented by a bipartite graph between the input and output ports, where each edge $(i,o)$ with demand $d_{i,o}^j$ means that $d_{i,o}^j$ units of packets must be delivered from port $i$ to port $o$. To complete co-flow $j$, we must satisfy all of its demands. Due to capacity constraints, a port can only transmit (or receive) one unit of data in unit time. A feasible schedule at each time $t$ must therefore be a bipartite matching. We consider co-flow scheduling and seek to optimize the popular objective of total weighted completion time. Our main result is a $(2+ε)$-approximation for this problem, which is essentially tight, as the problem is hard to approximate within a factor of $(2 - ε)$. This improves upon the previous best known 4-approximation. Further, our result holds even when jobs have release times without any loss in the approximation guarantee. The key idea of our approach is to construct a continuous-time schedule using a configuration linear program and interpret each job's completion time therein as the job's deadline. The continuous-time schedule serves as a witness schedule meeting the discovered deadlines, which allows us to reduce the problem to a deadline-constrained scheduling problem. * This result is flawed; see the first page for the details.
Lenient Multi-Agent Deep Reinforcement Learning
Venue: arXiv cs.MA 2018
Year: 2018

Much of the success of single agent deep reinforcement learning (DRL) in recent years can be attributed to the use of experience replay memories (ERM), which allow Deep Q-Networks (DQNs) to be trained efficiently through sampling stored state transitions. However, care is required when using ERMs for multi-agent deep reinforcement learning (MA-DRL), as stored transitions can become outdated because agents update their policies in parallel [11]. In this work we apply leniency [23] to MA-DRL. Lenient agents map state-action pairs to decaying temperature values that control the amount of leniency applied towards negative policy updates that are sampled from the ERM. This introduces optimism in the value-function update, and has been shown to facilitate cooperation in tabular fully-cooperative multi-agent reinforcement learning problems. We evaluate our Lenient-DQN (LDQN) empirically against the related Hysteretic-DQN (HDQN) algorithm [22] as well as a modified version we call scheduled-HDQN, that uses average reward learning near terminal states. Evaluations take place in extended variations of the Coordinated Multi-Agent Object Transportation Problem (CMOTP) [8] which include fully-cooperative sub-tasks and stochastic rewards. We find that LDQN agents are more likely to converge to the optimal policy in a stochastic reward CMOTP compared to standard and scheduled-HDQN agents.
Cloud-based or On-device: An Empirical Study of Mobile Deep Inference
Venue: arXiv cs.PF 2018
Year: 2018

Modern mobile applications are benefiting significantly from the advancement in deep learning, e.g., implementing real-time image recognition and conversational system. Given a trained deep learning model, applications usually need to perform a series of matrix operations based on the input data, in order to infer possible output values. Because of computational complexity and size constraints, these trained models are often hosted in the cloud. To utilize these cloud-based models, mobile apps will have to send input data over the network. While cloud-based deep learning can provide reasonable response time for mobile apps, it restricts the use case scenarios, e.g. mobile apps need to have network access. With mobile specific deep learning optimizations, it is now possible to employ on-device inference. However, because mobile hardware, such as GPU and memory size, can be very limited when compared to its desktop counterpart, it is important to understand the feasibility of this new on-device deep learning inference architecture. In this paper, we empirically evaluate the inference performance of three Convolutional Neural Networks (CNNs) using a benchmark Android application we developed. Our measurement and analysis suggest that on-device inference can cost up to two orders of magnitude greater response time and energy when compared to cloud-based inference, and that loading model and computing probability are two performance bottlenecks for on-device deep inferences.
Sorting and Transforming Program Repair Ingredients via Deep Learning Code Similarities
Venue: arXiv cs.SE 2018
Year: 2018

In the field of automated program repair, the redundancy assumption claims large programs contain the seeds of their own repair. However, most redundancy-based program repair techniques do not reason about the repair ingredients---the code that is reused to craft a patch. We aim to reason about the repair ingredients by using code similarities to prioritize and transform statements in a codebase for patch generation. Our approach, DeepRepair, relies on deep learning to reason about code similarities. Code fragments at well-defined levels of granularity in a codebase can be sorted according to their similarity to suspicious elements (i.e., code elements that contain suspicious statements) and statements can be transformed by mapping out-of-scope identifiers to similar identifiers in scope. We examined these new search strategies for patch generation with respect to effectiveness from the viewpoint of a software maintainer. Our comparative experiments were executed on six open-source Java projects including 374 buggy program revisions and consisted of 19,949 trials spanning 2,616 days of computation time. DeepRepair's search strategy using code similarities generally found compilable ingredients faster than the baseline, jGenProg, but this improvement neither yielded test-adequate patches in fewer attempts (on average) nor found significantly more patches than the baseline. Although the patch counts were not statistically different, there were notable differences between the nature of DeepRepair patches and baseline patches. The results demonstrate that our learning-based approach finds patches that cannot be found by existing redundancy-based repair techniques.
Deterministic Memory Abstraction and Supporting Multicore System Architecture
Venue: arXiv cs.AR 2018
Year: 2018

Poor time predictability of multicore processors has been a long-standing challenge in the real-time systems community. In this paper, we make a case that a fundamental problem that prevents efficient and predictable real-time computing on multicore is the lack of a proper memory abstraction to express memory criticality, which cuts across various layers of the system: the application, OS, and hardware. We, therefore, propose a new holistic resource management approach driven by a new memory abstraction, which we call Deterministic Memory. The key characteristic of deterministic memory is that the platform - the OS and hardware - guarantees small and tightly bounded worst-case memory access timing. In contrast, we call the conventional memory abstraction as best-effort memory in which only highly pessimistic worst-case bounds can be achieved. We propose to utilize both abstractions to achieve high time predictability but without significantly sacrificing performance. We present deterministic memory-aware OS and architecture designs, including OS-level page allocator, hardware-level cache, and DRAM controller designs. We implement the proposed OS and architecture extensions on Linux and gem5 simulator. Our evaluation results, using a set of synthetic and real-world benchmarks, demonstrate the feasibility and effectiveness of our approach.
Wide Inference Network for Image Denoising via Learning Pixel-distribution Prior
Venue: arXiv cs.CV 2018
Year: 2018

We explore an innovative strategy for image denoising by using convolutional neural networks (CNN) to learn similar pixel-distribution features from noisy images. Many types of image noise follow a certain pixel-distribution in common, such as additive white Gaussian noise (AWGN). By increasing CNN's width with larger reception fields and more channels in each layer, CNNs can reveal the ability to extract more accurate pixel-distribution features. The key to our approach is a discovery that wider CNNs with more convolutions tend to learn the similar pixel-distribution features, which reveals a new strategy to solve low-level vision problems effectively that the inference mapping primarily relies on the priors behind the noise property instead of deeper CNNs with more stacked nonlinear layers. We evaluate our work, Wide inference Networks (WIN), on AWGN and demonstrate that by learning pixel-distribution features from images, WIN-based network consistently achieves significantly better performance than current state-of-the-art deep CNN-based methods in both quantitative and visual evaluations. \textit{Code and models are available at \url{https://github.com/cswin/WIN}}.
An independent axiomatisation for free short-circuit logic
Venue: arXiv cs.LO 2018
Year: 2018

Short-circuit evaluation denotes the semantics of propositional connectives in which the second argument is evaluated only if the first argument does not suffice to determine the value of the expression. Free short-circuit logic is the equational logic in which compound statements are evaluated from left to right, while atomic evaluations are not memorised throughout the evaluation, i.e., evaluations of distinct occurrences of an atom in a compound statement may yield different truth values. We provide a simple semantics for free SCL and an independent axiomatisation. Finally, we discuss evaluation strategies, some other SCLs, and side effects.
Low-complexity implementation of convex optimization-based phase retrieval
Venue: arXiv cs.IT 2018
Year: 2018

Phase retrieval has important applications in optical imaging, communications and sensing. Lifting the dimensionality of the problem allows phase retrieval to be approximated as a convex optimization problem in a higher-dimensional space. Convex optimization-based phase retrieval has been shown to yield high accuracy, yet its low-complexity implementation has not been explored. In this paper, we study three fundamental approaches for its low-complexity implementation: the projected gradient method, the Nesterov accelerated gradient method, and the alternating direction method of multipliers (ADMM) method. We derive the corresponding estimation algorithms and evaluate their complexities. We compare their performance in the application area of direct-detection mode-division multiplexing. We demonstrate that they yield negligible estimation penalties (less than 0.2 dB for transmitter processing and less than 0.6 dB for receiver equalization) while yielding low computational cost, as their implementation complexities all scale quadratically in the number of unknown parameters. Among the three methods, ADMM achieves convergence after the smallest number of iterations.
FDTD: solving 1+1D delay PDE in parallel
Venue: arXiv cs.MS 2018
Year: 2018

We present a proof of concept for solving a 1+1D complex-valued, delay partial differential equation (PDE) that emerges in the study of waveguide quantum electrodynamics (QED) by adapting the finite-difference time-domain (FDTD) method. The delay term is spatially non-local, rendering conventional approaches such as the method of lines inapplicable. We show that by properly designing the grid and by supplying the (partial) exact solution as the boundary condition, the delay PDE can be numerically solved. In addition, we demonstrate that while the delay imposes strong data dependency, multi-thread parallelization can nevertheless be applied to such a problem. Our code provides a numerically exact solution to the time-dependent multi-photon scattering problem in waveguide QED.