OpenRaiser/Intern-Atlas huggingface dataset:
Quantified Markov Logic Networks
Venue: arXiv cs.AI 2018
Year: 2018

Markov Logic Networks (MLNs) are well-suited for expressing statistics such as "with high probability a smoker knows another smoker" but not for expressing statements such as "there is a smoker who knows most other smokers", which is necessary for modeling, e.g. influencers in social networks. To overcome this shortcoming, we study quantified MLNs which generalize MLNs by introducing statistical universal quantifiers, allowing to express also the latter type of statistics in a principled way. Our main technical contribution is to show that the standard reasoning tasks in quantified MLNs, maximum a posteriori and marginal inference, can be reduced to their respective MLN counterparts in polynomial time.
ReCoNet: Real-time Coherent Video Style Transfer Network
Venue: arXiv cs.CV 2018
Year: 2018

Image style transfer models based on convolutional neural networks usually suffer from high temporal inconsistency when applied to videos. Some video style transfer models have been proposed to improve temporal consistency, yet they fail to guarantee fast processing speed, nice perceptual style quality and high temporal consistency at the same time. In this paper, we propose a novel real-time video style transfer model, ReCoNet, which can generate temporally coherent style transfer videos while maintaining favorable perceptual styles. A novel luminance warping constraint is added to the temporal loss at the output level to capture luminance changes between consecutive frames and increase stylization stability under illumination effects. We also propose a novel feature-map-level temporal loss to further enhance temporal consistency on traceable objects. Experimental results indicate that our model exhibits outstanding performance both qualitatively and quantitatively.
A Weakly Supervised Adaptive DenseNet for Classifying Thoracic Diseases and Identifying Abnormalities
Venue: arXiv cs.CV 2018
Year: 2018

We present a weakly supervised deep learning model for classifying thoracic diseases and identifying abnormalities in chest radiography. In this work, instead of learning from medical imaging data with region-level annotations, our model was merely trained on imaging data with image-level labels to classify diseases, and is able to identify abnormal image regions simultaneously. Our model consists of a customized pooling structure and an adaptive DenseNet front-end, which can effectively recognize possible disease features for classification and localization tasks. Our method has been validated on the publicly available ChestX-ray14 dataset. Experimental results have demonstrated that our classification and localization prediction performance achieved significant improvement over the previous models on the ChestX-ray14 dataset. In summary, our network can produce accurate disease classification and localization, which can potentially support clinical decisions.
A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners
Venue: arXiv cs.DS 2018
Year: 2018

Given a 2-edge connected, unweighted, and undirected graph $G$ with $n$ vertices and $m$ edges, a $σ$-tree spanner is a spanning tree $T$ of $G$ in which the ratio between the distance in $T$ of any pair of vertices and the corresponding distance in $G$ is upper bounded by $σ$. The minimum value of $σ$ for which $T$ is a $σ$-tree spanner of $G$ is also called the {\em stretch factor} of $T$. We address the fault-tolerant scenario in which each edge $e$ of a given tree spanner may temporarily fail and has to be replaced by a {\em best swap edge}, i.e. an edge that reconnects $T-e$ at a minimum stretch factor. More precisely, we design an $O(n^2)$ time and space algorithm that computes a best swap edge of every tree edge. Previously, an $O(n^2 \log^4 n)$ time and $O(n^2+m\log^2n)$ space algorithm was known for edge-weighted graphs [Bilò et al., ISAAC 2017]. Even if our improvements on both the time and space complexities are of a polylogarithmic factor, we stress the fact that the design of a $o(n^2)$ time and space algorithm would be considered a breakthrough.
Playing against Nature: causal discovery for decision making under uncertainty
Venue: arXiv cs.AI 2018
Year: 2018

We consider decision problems under uncertainty where the options available to a decision maker and the resulting outcome are related through a causal mechanism which is unknown to the decision maker. We ask how a decision maker can learn about this causal mechanism through sequential decision making as well as using current causal knowledge inside each round in order to make better choices had she not considered causal knowledge and propose a decision making procedure in which an agent holds \textit{beliefs} about her environment which are used to make a choice and are updated using the observed outcome. As proof of concept, we present an implementation of this causal decision making model and apply it in a simple scenario. We show that the model achieves a performance similar to the classic Q-learning while it also acquires a causal model of the environment.
Efficient Rational Proofs with Strong Utility-Gap Guarantees
Venue: arXiv cs.GT 2018
Year: 2018

As modern computing moves towards smaller devices and powerful cloud platforms, more and more computation is being delegated to powerful service providers. Interactive proofs are a widely-used model to design efficient protocols for verifiable computation delegation. Rational proofs are payment-based interactive proofs. The payments are designed to incentivize the provers to give correct answers. If the provers misreport the answer then they incur a payment loss of at least 1/u, where u is the utility gap of the protocol. In this work, we tightly characterize the power of rational proofs that are super efficient, that is, require only logarithmic time and communication for verification. We also characterize the power of single-round rational protocols that require only logarithmic space and randomness for verification. Our protocols have strong (that is, polynomial, logarithmic, and even constant) utility gap. Finally, we show when and how rational protocols can be converted to give the completeness and soundness guarantees of classical interactive proofs.
A New Paradigm for Fault-Tolerant Computing with Interconnect Crosstalks
Venue: arXiv cs.AR 2018
Year: 2018

The CMOS integrated chips at advanced technology nodes are becoming more vulnerable to various sources of faults like manufacturing imprecisions, variations, aging, etc. Additionally, the intentional fault attacks (e.g., high power microwave, cybersecurity threats, etc.) and environmental effects (i.e., radiation) also pose reliability threats to integrated circuits. Though the traditional hardware redundancy-based techniques like Triple Modular Redundancy (TMR), Quadded (QL) Logic etc. mitigate the risk to some extent, they add huge hardware overhead and are not very effective. Truly polymorphic circuits that are inherently capable of achieving multiple functionalities in a limited footprint could enhance the faultresilience/recovery of the circuits with limited overhead. We demonstrate a novel crosstalk logic based polymorphic circuit approach to achieve compact and efficient fault resilient circuits. We show a range of polymorphic primitive gates and their usage in a functional unit. The functional unit is a single arithmetic circuit that is capable of delivering Multiplication/Sorting/Addition output depending on the control inputs. Using such polymorphic computing units in an ALU would imply that a correct path for functional output is possible even when 2/3rd of the ALU is damaged. Our comparison results with respect to existing polymorphic techniques and CMOS reveal 28% and 62% reduction in transistor count respectively for the same functionalities. In conjunction with fault detection algorithms, the proposed polymorphic circuit concept can be transformative for fault tolerant circuit design directions with minimum overhead.
Qos-Based Web Service Discovery And Selection Using Machine Learning
Venue: arXiv cs.CY 2018
Year: 2018

In service computing, the same target functions can be achieved by multiple Web services from different providers. Due to the functional similarities, the client needs to consider the non-functional criteria. However, Quality of Service provided by the developer suffers from scarcity and lack of reliability. In addition, the reputation of the service providers is an important factor, especially those with little experience, to select a service. Most of the previous studies were focused on the user's feedbacks for justifying the selection. Unfortunately, not all the users provide the feedback unless they had extremely good or bad experience with the service. In this vision paper, we propose a novel architecture for the web service discovery and selection. The core component is a machine learning based methodology to predict the QoS properties using source code metrics. The credibility value and previous usage count are used to determine the reputation of the service.
Understanding Visual Ads by Aligning Symbols and Objects using Co-Attention
Venue: arXiv cs.CV 2018
Year: 2018

We tackle the problem of understanding visual ads where given an ad image, our goal is to rank appropriate human generated statements describing the purpose of the ad. This problem is generally addressed by jointly embedding images and candidate statements to establish correspondence. Decoding a visual ad requires inference of both semantic and symbolic nuances referenced in an image and prior methods may fail to capture such associations especially with weakly annotated symbols. In order to create better embeddings, we leverage an attention mechanism to associate image proposals with symbols and thus effectively aggregate information from aligned multimodal representations. We propose a multihop co-attention mechanism that iteratively refines the attention map to ensure accurate attention estimation. Our attention based embedding model is learned end-to-end guided by a max-margin loss function. We show that our model outperforms other baselines on the benchmark Ad dataset and also show qualitative results to highlight the advantages of using multihop co-attention.
Semantic Instance Meets Salient Object: Study on Video Semantic Salient Instance Segmentation
Venue: arXiv cs.CV 2018
Year: 2018

Focusing on only semantic instances that only salient in a scene gains more benefits for robot navigation and self-driving cars than looking at all objects in the whole scene. This paper pushes the envelope on salient regions in a video to decompose them into semantically meaningful components, namely, semantic salient instances. We provide the baseline for the new task of video semantic salient instance segmentation (VSSIS), that is, Semantic Instance - Salient Object (SISO) framework. The SISO framework is simple yet efficient, leveraging advantages of two different segmentation tasks, i.e. semantic instance segmentation and salient object segmentation to eventually fuse them for the final result. In SISO, we introduce a sequential fusion by looking at overlapping pixels between semantic instances and salient regions to have non-overlapping instances one by one. We also introduce a recurrent instance propagation to refine the shapes and semantic meanings of instances, and an identity tracking to maintain both the identity and the semantic meaning of instances over the entire video. Experimental results demonstrated the effectiveness of our SISO baseline, which can handle occlusions in videos. In addition, to tackle the task of VSSIS, we augment the DAVIS-2017 benchmark dataset by assigning semantic ground-truth for salient instance labels, obtaining SEmantic Salient Instance Video (SESIV) dataset. Our SESIV dataset consists of 84 high-quality video sequences with pixel-wisely per-frame ground-truth labels.
Near-Optimal Distance Emulator for Planar Graphs
Venue: arXiv cs.DS 2018
Year: 2018

Given a graph $G$ and a set of terminals $T$, a \emph{distance emulator} of $G$ is another graph $H$ (not necessarily a subgraph of $G$) containing $T$, such that all the pairwise distances in $G$ between vertices of $T$ are preserved in $H$. An important open question is to find the smallest possible distance emulator. We prove that, given any subset of $k$ terminals in an $n$-vertex undirected unweighted planar graph, we can construct in $\tilde O(n)$ time a distance emulator of size $\tilde O(\min(k^2,\sqrt{k\cdot n}))$. This is optimal up to logarithmic factors. The existence of such distance emulator provides a straightforward framework to solve distance-related problems on planar graphs: Replace the input graph with the distance emulator, and apply whatever algorithm available to the resulting emulator. In particular, our result implies that, on any unweighted undirected planar graph, one can compute all-pairs shortest path distances among $k$ terminals in $\tilde O(n)$ time when $k=O(n^{1/3})$.
Learning Fuzzy Set Representations of Partial Shapes on Dual Embedding Spaces
Venue: arXiv cs.GR 2018
Year: 2018

Modeling relations between components of 3D objects is essential for many geometry editing tasks. Existing techniques commonly rely on labeled components, which requires substantial annotation effort and limits components to a dictionary of predefined semantic parts. We propose a novel framework based on neural networks that analyzes an uncurated collection of 3D models from the same category and learns two important types of semantic relations among full and partial shapes: complementarity and interchangeability. The former helps to identify which two partial shapes make a complete plausible object, and the latter indicates that interchanging two partial shapes from different objects preserves the object plausibility. Our key idea is to jointly encode both relations by embedding partial shapes as fuzzy sets in dual embedding spaces. We model these two relations as fuzzy set operations performed across the dual embedding spaces, and within each space, respectively. We demonstrate the utility of our method for various retrieval tasks that are commonly needed in geometric modeling interfaces.
Answering Hindsight Queries with Lifted Dynamic Junction Trees
Venue: arXiv cs.AI 2018
Year: 2018

The lifted dynamic junction tree algorithm (LDJT) efficiently answers filtering and prediction queries for probabilistic relational temporal models by building and then reusing a first-order cluster representation of a knowledge base for multiple queries and time steps. We extend LDJT to (i) solve the smoothing inference problem to answer hindsight queries by introducing an efficient backward pass and (ii) discuss different options to instantiate a first-order cluster representation during a backward pass. Further, our relational forward backward algorithm makes hindsight queries to the very beginning feasible. LDJT answers multiple temporal queries faster than the static lifted junction tree algorithm on an unrolled model, which performs smoothing during message passing.
Cimple: Instruction and Memory Level Parallelism
Venue: arXiv cs.PL 2018
Year: 2018

Modern out-of-order processors have increased capacity to exploit instruction level parallelism (ILP) and memory level parallelism (MLP), e.g., by using wide superscalar pipelines and vector execution units, as well as deep buffers for in-flight memory requests. These resources, however, often exhibit poor utilization rates on workloads with large working sets, e.g., in-memory databases, key-value stores, and graph analytics, as compilers and hardware struggle to expose ILP and MLP from the instruction stream automatically. In this paper, we introduce the IMLP (Instruction and Memory Level Parallelism) task programming model. IMLP tasks execute as coroutines that yield execution at annotated long-latency operations, e.g., memory accesses, divisions, or unpredictable branches. IMLP tasks are interleaved on a single thread, and integrate well with thread parallelism and vectorization. Our DSL embedded in C++, Cimple, allows exploration of task scheduling and transformations, such as buffering, vectorization, pipelining, and prefetching. We demonstrate state-of-the-art performance on core algorithms used in in-memory databases that operate on arrays, hash tables, trees, and skip lists. Cimple applications reach 2.5x throughput gains over hardware multithreading on a multi-core, and 6.4x single thread speedup.
Neonatal Pain Expression Recognition Using Transfer Learning
Venue: arXiv cs.CV 2018
Year: 2018

Transfer learning using pre-trained Convolutional Neural Networks (CNNs) has been successfully applied to images for different classification tasks. In this paper, we propose a new pipeline for pain expression recognition in neonates using transfer learning. Specifically, we propose to exploit a pre-trained CNN that was originally trained on a relatively similar dataset for face recognition (VGG Face) as well as CNNs that were pre-trained on a relatively different dataset for image classification (iVGG F,M, and S) to extract deep features from neonates' faces. In the final stage, several supervised machine learning classifiers are trained to classify neonates' facial expression into pain or no pain expression. The proposed pipeline achieved, on a testing dataset, 0.841 AUC and 90.34 accuracy, which is approx. 7 higher than the accuracy of handcrafted traditional features. We also propose to combine deep features with traditional features and hypothesize that the mixed features would improve pain classification performance. Combining deep features with traditional features achieved 92.71 accuracy and 0.948 AUC. These results show that transfer learning, which is a faster and more practical option than training CNN from the scratch, can be used to extract useful features for pain expression recognition in neonates. It also shows that combining deep features with traditional handcrafted features is a good practice to improve the performance of pain expression recognition and possibly the performance of similar applications.
Ranked Reward: Enabling Self-Play Reinforcement Learning for Combinatorial Optimization
Venue: arXiv cs.LG 2018
Year: 2018

Adversarial self-play in two-player games has delivered impressive results when used with reinforcement learning algorithms that combine deep neural networks and tree search. Algorithms like AlphaZero and Expert Iteration learn tabula-rasa, producing highly informative training data on the fly. However, the self-play training strategy is not directly applicable to single-player games. Recently, several practically important combinatorial optimisation problems, such as the travelling salesman problem and the bin packing problem, have been reformulated as reinforcement learning problems, increasing the importance of enabling the benefits of self-play beyond two-player games. We present the Ranked Reward (R2) algorithm which accomplishes this by ranking the rewards obtained by a single agent over multiple games to create a relative performance metric. Results from applying the R2 algorithm to instances of a two-dimensional and three-dimensional bin packing problems show that it outperforms generic Monte Carlo tree search, heuristic algorithms and integer programming solvers. We also present an analysis of the ranked reward mechanism, in particular, the effects of problem instances with varying difficulty and different ranking thresholds.
Tight bounds for popping algorithms
Venue: arXiv cs.DS 2018
Year: 2018

We sharpen run-time analysis for algorithms under the partial rejection sampling framework. Our method yields improved bounds for: the cluster-popping algorithm for approximating all-terminal network reliability; the cycle-popping algorithm for sampling rooted spanning trees; the sink-popping algorithm for sampling sink-free orientations. In all three applications, our bounds are not only tight in order, but also optimal in constants.
An efficient quantum circuits optimizing scheme compared with QISKit
Venue: arXiv cs.ET 2018
Year: 2018

Recently, the development of quantum chips has made great progress-- the number of qubits is increasing and the fidelity is getting higher. However, qubits of these chips are not always fully connected, which sets additional barriers for implementing quantum algorithms and programming quantum programs. In this paper, we introduce a general circuit optimizing scheme, which can efficiently adjust and optimize quantum circuits according to arbitrary given qubits' layout by adding additional quantum gates, exchanging qubits and merging single-qubit gates. Compared with the optimizing algorithm of IBM's QISKit, the quantum gates consumed by our scheme is 74.7%, and the execution time is only 12.9% on average.
Recommendation Systems and Self Motivated Users
Venue: arXiv cs.GT 2018
Year: 2018

Modern recommendation systems rely on the wisdom of the crowd to learn the optimal course of action. This induces an inherent mis-alignment of incentives between the system's objective to learn (explore) and the individual users' objective to take the contemporaneous optimal action (exploit). The design of such systems must account for this and also for additional information available to the users. A prominent, yet simple, example is when agents arrive sequentially and each agent observes the action and reward of his predecessor. We provide an incentive compatible and asymptotically optimal mechanism for that setting. The complexity of the mechanism suggests that the design of such systems for general settings is a challenging task.
Transfer with Model Features in Reinforcement Learning
Venue: arXiv cs.LG 2018
Year: 2018

A key question in Reinforcement Learning is which representation an agent can learn to efficiently reuse knowledge between different tasks. Recently the Successor Representation was shown to have empirical benefits for transferring knowledge between tasks with shared transition dynamics. This paper presents Model Features: a feature representation that clusters behaviourally equivalent states and that is equivalent to a Model-Reduction. Further, we present a Successor Feature model which shows that learning Successor Features is equivalent to learning a Model-Reduction. A novel optimization objective is developed and we provide bounds showing that minimizing this objective results in an increasingly improved approximation of a Model-Reduction. Further, we provide transfer experiments on randomly generated MDPs which vary in their transition and reward functions but approximately preserve behavioural equivalence between states. These results demonstrate that Model Features are suitable for transfer between tasks with varying transition and reward functions.
Learning Personalized Representation for Inverse Problems in Medical Imaging Using Deep Neural Network
Venue: arXiv cs.CV 2018
Year: 2018

Recently deep neural networks have been widely and successfully applied in computer vision tasks and attracted growing interests in medical imaging. One barrier for the application of deep neural networks to medical imaging is the need of large amounts of prior training pairs, which is not always feasible in clinical practice. In this work we propose a personalized representation learning framework where no prior training pairs are needed, but only the patient's own prior images. The representation is expressed using a deep neural network with the patient's prior images as network input. We then applied this novel image representation to inverse problems in medical imaging in which the original inverse problem was formulated as a constraint optimization problem and solved using the alternating direction method of multipliers (ADMM) algorithm. Anatomically guided brain positron emission tomography (PET) image reconstruction and image denoising were employed as examples to demonstrate the effectiveness of the proposed framework. Quantification results based on simulation and real datasets show that the proposed personalized representation framework outperform other widely adopted methods.