OpenRaiser/Intern-Atlas huggingface dataset:
A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints
Venue: arXiv cs.DS 2018
Year: 2018

Motivated by applications in machine learning, such as subset selection and data summarization, we consider the problem of maximizing a monotone submodular function subject to mixed packing and covering constraints. We present a tight approximation algorithm that for any constant $ε>0$ achieves a guarantee of $1-\frac{1}{\mathrm{e}}-ε$ while violating only the covering constraints by a multiplicative factor of $1-ε$. Our algorithm is based on a novel enumeration method, which unlike previous known enumeration techniques, can handle both packing and covering constraints. We extend the above main result by additionally handling a matroid independence constraints as well as finding (approximate) pareto set optimal solutions when multiple submodular objectives are present. Finally, we propose a novel and purely combinatorial dynamic programming approach that can be applied to several special cases of the problem yielding not only {\em deterministic} but also considerably faster algorithms. For example, for the well studied special case of only packing constraints (Kulik {\em et. al.} [Math. Oper. Res. `13] and Chekuri {\em et. al.} [FOCS `10]), we are able to present the first deterministic non-trivial approximation algorithm. We believe our new combinatorial approach might be of independent interest.
UNIQ: Uniform Noise Injection for Non-Uniform Quantization of Neural Networks
Venue: arXiv cs.LG 2018
Year: 2018

We present a novel method for neural network quantization that emulates a non-uniform $k$-quantile quantizer, which adapts to the distribution of the quantized parameters. Our approach provides a novel alternative to the existing uniform quantization techniques for neural networks. We suggest to compare the results as a function of the bit-operations (BOPS) performed, assuming a look-up table availability for the non-uniform case. In this setup, we show the advantages of our strategy in the low computational budget regime. While the proposed solution is harder to implement in hardware, we believe it sets a basis for new alternatives to neural networks quantization.
Of Wines and Reviews: Measuring and Modeling the Vivino Wine Social Network
Venue: arXiv cs.CY 2018
Year: 2018

This paper presents an analysis of social experiences around wine consumption through the lens of Vivino, a social network for wine enthusiasts with over 26 million users worldwide. We compare users' perceptions of various wine types and regional styles across both New and Old World wines, examining them across price ranges, vintages, regions, varietals, and blends. Among other things, we find that ratings provided by Vivino users are not biased by cost. We then study how wine characteristics, language in wine reviews, and the distribution of wine ratings can be combined to develop prediction models. More specifically, we model user behavior to develop a regression model for predicting wine ratings, and a classifier for determining user review preferences.
Optimal Scheduling for Exposed Datapath Architectures with Buffered Processing Units by ASP
Venue: arXiv cs.LO 2018
Year: 2018

Conventional processor architectures are restricted in exploiting instruction level parallelism (ILP) due to the relatively low number of programmer-visible registers. Therefore, more recent processor architectures expose their datapaths so that the compiler (1) can schedule parallel instructions to different processing units and (2) can make effective use of local storage of the processing units. Among these architectures, the Synchronous Control Asynchronous Dataflow (SCAD) architecture is a new exposed datapath architecture whose processing units are equipped with first-in first-out (FIFO) buffers at their input and output ports. In contrast to register-based machines, the optimal code generation for SCAD is still a matter of research. In particular, SAT and SMT solvers were used to generate optimal resource constrained and optimal time constrained schedules for SCAD, respectively. As Answer Set Programming (ASP) offers better flexibility in handling such scheduling problems, we focus in this paper on using an answer set solver for both resource and time constrained optimal SCAD code generation. As a major benefit of using ASP, we are able to generate \emph{all} optimal schedules for a given program which allows one to study their properties. Furthermore, the experimental results of this paper demonstrate that the answer set solver can compete with SAT solvers and outperforms SMT solvers. \emph{This paper is under consideration for acceptance in TPLP.}
Towards Deeper Generative Architectures for GANs using Dense connections
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we present the result of adopting skip connections and dense layers, previously used in image classification tasks, in the Fisher GAN implementation. We have experimented with different numbers of layers and inserting these connections in different sections of the network. Our findings suggests that networks implemented with the connections produce better images than the baseline, and the number of connections added has only slight effect on the result.
Holistic Management of the GPGPU Memory Hierarchy to Manage Warp-level Latency Tolerance
Venue: arXiv cs.AR 2018
Year: 2018

In a modern GPU architecture, all threads within a warp execute the same instruction in lockstep. For a memory instruction, this can lead to memory divergence: the memory requests for some threads are serviced early, while the remaining requests incur long latencies. This divergence stalls the warp, as it cannot execute the next instruction until all requests from the current instruction complete. In this work, we make three new observations. First, GPGPU warps exhibit heterogeneous memory divergence behavior at the shared cache: some warps have most of their requests hit in the cache, while other warps see most of their request miss. Second, a warp retains the same divergence behavior for long periods of execution. Third, requests going to the shared cache can incur queuing delays as large as hundreds of cycles, exacerbating the effects of memory divergence. We propose a set of techniques, collectively called Memory Divergence Correction (MeDiC), that reduce the negative performance impact of memory divergence and cache queuing. MeDiC delivers an average speedup of 21.8%, and 20.1% higher energy efficiency, over a state-of-the-art GPU cache management mechanism across 15 different GPGPU applications.
VLC Systems with Fixed-Rate Transmissions under Statistical Queueing Constraints
Venue: arXiv cs.IT 2018
Year: 2018

Cross-layer analysis has been gaining an increasing attention as a powerful tool to study and assess different quality-of-service (QoS) mechanisms in wireless networks. Regarding the physical and data-link layers, in this paper we provide a cross-layer study for visible light communication (VLC) systems operating under statistical QoS constraints, which are inflicted as limits on the delay violation and buffer overflow probabilities. We assume that the VLC access point (AP) is unaware of the channel conditions, thus the AP sends the data at a fixed rate. Under this assumption, and considering an ON-OFF data source, we employ the maximum average data arrival rate at the AP buffer and the non-asymptotic bounds on buffering delay as the main performance measures. Through numerical results, we illustrate the impacts of different physical and data-link parameters on the system performance.
Fast and scalable learning of neuro-symbolic representations of biomedical knowledge
Venue: arXiv cs.AI 2018
Year: 2018

In this work we address the problem of fast and scalable learning of neuro-symbolic representations for general biological knowledge. Based on a recently published comprehensive biological knowledge graph (Alshahrani, 2017) that was used for demonstrating neuro-symbolic representation learning, we show how to train fast (under 1 minute) log-linear neural embeddings of the entities. We utilize these representations as inputs for machine learning classifiers to enable important tasks such as biological link prediction. Classifiers are trained by concatenating learned entity embeddings to represent entity relations, and training classifiers on the concatenated embeddings to discern true relations from automatically generated negative examples. Our simple embedding methodology greatly improves on classification error compared to previously published state-of-the-art results, yielding a maximum increase of $+0.28$ F-measure and $+0.22$ ROC AUC scores for the most difficult biological link prediction problem. Finally, our embedding approach is orders of magnitude faster to train ($\leq$ 1 minute vs. hours), much more economical in terms of embedding dimensions ($d=50$ vs. $d=512$), and naturally encodes the directionality of the asymmetric biological relations, that can be controlled by the order with which we concatenate the embeddings.
A novel method for depicting academic disciplines through Google Scholar Citations: The case of Bibliometrics
Venue: arXiv cs.DL 2018
Year: 2018

This article describes a procedure to generate a snapshot of the structure of a specific scientific community and their outputs based on the information available in Google Scholar Citations (GSC). We call this method MADAP (Multifaceted Analysis of Disciplines through Academic Profiles). The international community of researchers working in Bibliometrics, Scientometrics, Informetrics, Webometrics, and Altmetrics was selected as a case study. The records of the top 1,000 most cited documents by these authors according to GSC were manually processed to fill any missing information and deduplicate fields like the journal titles and book publishers. The results suggest that it is feasible to use GSC and the MADAP method to produce an accurate depiction of the community of researchers working in Bibliometrics (both specialists and occasional researchers) and their publication habits (main publication venues such as journals and book publishers). Additionally, the wide document coverage of Google Scholar (specially books and book chapters) enables more comprehensive analyses of the documents published in a specific discipline than were previously possible with other citation indexes, finally shedding light on what until now had been a blind spot in most citation analyses.
Adversarial Task Assignment
Venue: arXiv cs.GT 2018
Year: 2018

The problem of assigning tasks to workers is of long-standing fundamental importance. Examples of this include the classical problem of assigning computing tasks to nodes in a distributed computing environment, assigning jobs to robots, and crowdsourcing. Extensive research into this problem generally addresses important issues such as uncertainty and incentives. However, the problem of adversarial tampering with the task assignment process has not received as much attention. We are concerned with a particular adversarial setting where an attacker may target a set of workers in order to prevent the tasks assigned to these workers from being completed. When all tasks are homogeneous, we provide an efficient algorithm for computing the optimal assignment. When tasks are heterogeneous, we show that the adversarial assignment problem is NP-Hard, and present an algorithm for solving it approximately. Our theoretical results are accompanied by extensive experiments showing the effectiveness of our algorithms.
Practical Low-Dimensional Halfspace Range Space Sampling
Venue: arXiv cs.CG 2018
Year: 2018

We develop, analyze, implement, and compare new algorithms for creating $\varepsilon$-samples of range spaces defined by halfspaces which have size sub-quadratic in $1/\varepsilon$, and have runtime linear in the input size and near-quadratic in $1/\varepsilon$. The key to our solution is an efficient construction of partition trees. Despite not requiring any techniques developed after the early 1990s, apparently such a result was not ever explicitly described. We demonstrate that our implementations, including new implementations of several variants of partition trees, do indeed run in time linear in the input, appear to run linear in output size, and observe smaller error for the same size sample compared to the ubiquitous random sample (which requires size quadratic in $1/\varepsilon$). This result has direct applications in speeding up discrepancy evaluation, approximate range counting, and spatial anomaly detection.
Exploiting Answer Set Programming with External Sources for Meta-Interpretive Learning
Venue: arXiv cs.LO 2018
Year: 2018

Meta-Interpretive Learning (MIL) learns logic programs from examples by instantiating meta-rules, which is implemented by the Metagol system based on Prolog. Viewing MIL-problems as combinatorial search problems, they can alternatively be solved by employing Answer Set Programming (ASP), which may result in performance gains as a result of efficient conflict propagation. However, a straightforward ASP-encoding of MIL results in a huge search space due to a lack of procedural bias and the need for grounding. To address these challenging issues, we encode MIL in the HEX-formalism, which is an extension of ASP that allows us to outsource the background knowledge, and we restrict the search space to compensate for a procedural bias in ASP. This way, the import of constants from the background knowledge can for a given type of meta-rules be limited to relevant ones. Moreover, by abstracting from term manipulations in the encoding and by exploiting the HEX interface mechanism, the import of such constants can be entirely avoided in order to mitigate the grounding bottleneck. An experimental evaluation shows promising results.
A Cyberinfrastructure for BigData Transportation Engineering
Venue: arXiv cs.OH 2018
Year: 2018

Big Data-driven transportation engineering has the potential to improve utilization of road infrastructure, decrease traffic fatalities, improve fuel consumption, decrease construction worker injuries, among others. Despite these benefits, research on Big Data-driven transportation engineering is difficult today due to the computational expertise required to get started. This work proposes BoaT, a transportation-specific programming language, and it's Big Data infrastructure that is aimed at decreasing this barrier to entry. Our evaluation that uses over two dozen research questions from six categories show that research is easier to realize as a BoaT computer program, an order of magnitude faster when this program is run, and exhibits 12-14x decrease in storage requirements.
A Canonical Image Set for Examining and Comparing Image Processing Algorithms
Venue: arXiv cs.CV 2018
Year: 2018

The purpose of this paper is to introduce a set of four test images containing features and structures that can facilitate effective examination and comparison of image processing algorithms. More specifically, the images are designed to more explicitly expose the characteristic properties of algorithms for image compression, virtual resolution adjustment, and enhancement. This set was developed at the Naval Research Laboratory (NRL) in the late 1990s as a more rigorous alternative to Lena and other images that have come into common use for purely ad hoc reasons with little or no rigorous consideration of their suitability. The increasing number of test images appearing in the literature not only makes it more difficult to compare results from different papers, it also introduces the potential for cherry-picking to influence results. The key contribution of this paper is the proposal to establish {\em some} canonical set to ensure that published results can be analyzed and compared in a rigorous way from one paper to another, and consideration of the four NRL images is proposed for this purpose.
URLLC-eMBB Slicing to Support VR Multimodal Perceptions over Wireless Cellular Systems
Venue: arXiv cs.IT 2018
Year: 2018

Virtual reality (VR) enables mobile wireless users to experience multimodal perceptions in a virtual space. In this paper we investigate the problem of concurrent support of visual and haptic perceptions over wireless cellular networks, with a focus on the downlink transmission phase. While the visual perception requires moderate reliability and maximized rate, the haptic perception requires fixed rate and high reliability. Hence, the visuo-haptic VR traffic necessitates the use of two different network slices: enhanced mobile broadband (eMBB) for visual perception and ultra-reliable and low latency communication (URLLC) for haptic perception. We investigate two methods by which these two slices share the downlink resources orthogonally and non-orthogonally, respectively. We compare these methods in terms of the just-noticeable difference (JND), an established measure in psychophysics, and show that non-orthogonal slicing becomes preferable under a higher target integrated-perceptual resolution and/or a higher target rate for haptic perceptions.
Realistic Multimedia Tools based on Physical Models: I. The Spectrum Analyzer and Animator (SA2)
Venue: arXiv cs.MM 2018
Year: 2018

The present sequence of two articles reports on a custom-built toolkit implementing a technique similar to multi-directional medical tomography to simulate and visualize the composite 3D structure of winds from hot close double stars. In such hot binaries, the light sources scanning and probing the composite wind volume are the bright "surfaces" (photospheres) of the individual stars. Then, as the Keplerian orbit is traced out and the geometry presented to the observer varies, each star constitutes an analyzer upon its companion's wind. In contrast to medical tomography, however, these targets are too far to be resolved spatially so we resort to modeling the ultraviolet (UV) spectral lines of certain wind ions (e.g., N+4, Si+3, C+3) whose shapes vary with Keplerian phase as the stars revolve around their common centre of mass. The flagships of the toolkit are the Spectrum Analyzer and Animator (SA 2 ) and the Binary 3D Renderer (B3dR). The SA 2 is the subject of the present article (paper I). It automates (a) the derivation of light curves from the observed spectra and (b) the generation of synthetic binary wind-line profiles which reproduce the morphologies and variabilities of the observed wind profiles. The second tool, the B3dR is discussed in paper II.
Tourist Navigation in Android Smartphone by using Emotion Generating Calculations and Mental State Transition Networks
Venue: arXiv cs.HC 2018
Year: 2018

Mental State Transition Network which consists of mental states connected to each other is a basic concept of approximating to human psychological and mental responses. It can represent transition from an emotional state to other one with stimulus by calculating Emotion Generating Calculations method. A computer agent can transit a mental state in MSTN based on analysis of emotion by EGC method. In this paper, the Andorid EGC which the agent works in Android smartphone can evaluate the feelings in the conversation. The tourist navigation system with the proposed technique in this paper will be expected to be an emotional oriented interface in Android smartphone.
PURE: Scalable Phase Unwrapping with Spatial Redundant Arcs
Venue: arXiv cs.OH 2018
Year: 2018

Phase unwrapping is a key problem in many coherent imaging systems, such as synthetic aperture radar (SAR) interferometry. A general formulation for redundant integration of finite differences for phase unwrapping (Costantini et al., 2010) was shown to produce a more reliable solution by exploiting redundant differential estimates. However, this technique requires a commercial linear programming solver for large-scale problems. For a linear cost function, we propose a method based on Dual Decomposition that breaks the given problem defined over a non-planar graph into tractable sub-problems over planar subgraphs. We also propose a decomposition technique that exploits the underlying graph structure for solving the sub-problems efficiently and guarantees asymptotic convergence to the globally optimal solution. The experimental results demonstrate that the proposed approach is comparable to the existing state-of-the-art methods in terms of the estimate with a better runtime and memory footprint.
A Deep Face Identification Network Enhanced by Facial Attributes Prediction
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we propose a new deep framework which predicts facial attributes and leverage it as a soft modality to improve face identification performance. Our model is an end to end framework which consists of a convolutional neural network (CNN) whose output is fanned out into two separate branches; the first branch predicts facial attributes while the second branch identifies face images. Contrary to the existing multi-task methods which only use a shared CNN feature space to train these two tasks jointly, we fuse the predicted attributes with the features from the face modality in order to improve the face identification performance. Experimental results show that our model brings benefits to both face identification as well as facial attribute prediction performance, especially in the case of identity facial attributes such as gender prediction. We tested our model on two standard datasets annotated by identities and face attributes. Experimental results indicate that the proposed model outperforms most of the current existing face identification and attribute prediction methods.
Deep learning approach to Fourier ptychographic microscopy
Venue: arXiv cs.CV 2018
Year: 2018

Convolutional neural networks (CNNs) have gained tremendous success in solving complex inverse problems. The aim of this work is to develop a novel CNN framework to reconstruct video sequence of dynamic live cells captured using a computational microscopy technique, Fourier ptychographic microscopy (FPM). The unique feature of the FPM is its capability to reconstruct images with both wide field-of-view (FOV) and high resolution, i.e. a large space-bandwidth-product (SBP), by taking a series of low resolution intensity images. For live cell imaging, a single FPM frame contains thousands of cell samples with different morphological features. Our idea is to fully exploit the statistical information provided by this large spatial ensemble so as to make predictions in a sequential measurement, without using any additional temporal dataset. Specifically, we show that it is possible to reconstruct high-SBP dynamic cell videos by a CNN trained only on the first FPM dataset captured at the beginning of a time-series experiment. Our CNN approach reconstructs a 12800X10800 pixels phase image using only ~25 seconds, a 50X speedup compared to the model-based FPM algorithm. In addition, the CNN further reduces the required number of images in each time frame by ~6X. Overall, this significantly improves the imaging throughput by reducing both the acquisition and computational times. The proposed CNN is based on the conditional generative adversarial network (cGAN) framework. Additionally, we also exploit transfer learning so that our pre-trained CNN can be further optimized to image other cell types. Our technique demonstrates a promising deep learning approach to continuously monitor large live-cell populations over an extended time and gather useful spatial and temporal information with sub-cellular resolution.