OpenRaiser/Intern-Atlas huggingface dataset:
Entropy supplementary conservation law for non-linear systems of PDEs with non-conservative terms: application to the modelling and analysis of complex fluid flows using computer algebra
Venue: arXiv cs.SC 2019
Year: 2019

In the present contribution, we investigate first-order nonlinear systems of partial differential equations which are constituted of two parts: a system of conservation laws and non-conservative first order terms. Whereas the theory of first-order systems of conservation laws is well established and the conditions for the existence of supplementary conservation laws, and more specifically of an entropy supplementary conservation law for smooth solutions, well known, there exists so far no general extension to obtain such supplementary conservation laws when non-conservative terms are present. We propose a framework in order to extend the existing theory and show that the presence of non-conservative terms somewhat complexifies the problem since numerous combinations of the conservative and non-conservative terms can lead to a supplementary conservation law. We then identify a restricted framework in order to design and analyze physical models of complex fluid flows by means of computer algebra and thus obtain the entire ensemble of possible combination of conservative and non-conservative terms with the objective of obtaining specifically an entropy supplementary conservation law. The theory as well as developed computer algebra tool are then applied to a Baer-Nunziato two-phase flow model and to a multicomponent plasma fluid model. The first one is a first-order fluid model, with non-conservative terms impacting on the linearly degenerate field and requires a closure since there is no way to derive interfacial quantities from averaging principles and we need guidance in order to close the pressure and velocity of the interface and the thermodynamics of the mixture. The second one involves first order terms for the heavy species coupled to second order terms for the electrons, the non-conservative terms impact the genuinely nonlinear fields and the model can be rigorously derived from kinetic theory. We show how the theory allows to recover the whole spectrum of closures obtained so far in the literature for the two-phase flow system as well as conditions when one aims at extending the thermodynamics and also applies to the plasma case, where we recover the usual entropy supplementary equation, thus assessing the effectiveness and scope of the proposed theory.
SpiNNaker 2: A 10 Million Core Processor System for Brain Simulation and Machine Learning
Venue: arXiv cs.ET 2019
Year: 2019

SpiNNaker is an ARM-based processor platform optimized for the simulation of spiking neural networks. This brief describes the roadmap in going from the current SPINNaker1 system, a 1 Million core machine in 130nm CMOS, to SpiNNaker2, a 10 Million core machine in 22nm FDSOI. Apart from pure scaling, we will take advantage of specific technology features, such as runtime adaptive body biasing, to deliver cutting-edge power consumption. Power management of the cores allows a wide range of workload adaptivity, i.e. processor power scales with the complexity and activity of the spiking network. Additional numerical accelerators will enhance the utility of SpiNNaker2 for simulation of spiking neural networks as well as for executing conventional deep neural networks. These measures should increase the simulation capacity of the machine by a factor $>$50. The interplay between the two domains, i.e. spiking and rate based, will provide an interesting field for algorithm exploration on SpiNNaker2. Apart from the platforms' traditional usage as a neuroscience exploration tool, the extended functionality opens up new application areas such as automotive AI, tactile internet, industry 4.0 and biomedical processing.
DeLottery: A Novel Decentralized Lottery System Based on Blockchain Technology
Venue: arXiv cs.DC 2019
Year: 2019

In this paper, we design DeLottery, a decentralized lottery system based on block chain technology and smart contracts. Lottery is a classical form of entertainment and charity for centuries. Facing the bottleneck of the combination between lottery and information technology, we use smart contracts and blockchain in decentralized, intelligent, and secure systems for lottery industries. Moreover, we are inspired by the algorithm of RANDAO, an outstanding way of random number generation in blockchain scenario. The components and the functions of the novel system are described in details. We implement DeLottery in a blockchain network and show functioning procedure and security of the proposed lottery system.
Graph-based Approach for Buffer-aware Timing Analysis of Heterogeneous Wormhole NoCs under Bursty Traffic
Venue: arXiv cs.PF 2019
Year: 2019

This paper addresses the problem of worst-case timing analysis of heterogeneous wormhole NoCs, i.e., routers with different buffer sizes and transmission speeds, when consecutive packet queuing (CPQ) occurs. The latter means that there are several consecutive packets of one flow queuing in the network. This scenario happens in the case of bursty traffic but also for non-schedulable traffic. Conducting such an analysis is known to be a challenging issue due to the sophisticated congestion patterns when enabling backpressure mechanisms. We tackle this problem through extending the applicability domain of our previous work for computing maximum delay bounds using Network Calculus, called Buffer-aware worst-case Timing Analysis (BATA). We propose a new Graph-based approach to improve the analysis of indirect blocking due to backpressure, while capturing the CPQ effect and keeping the information about dependencies between flows. Furthermore, the introduced approach improves the computation of indirect-blocking delay bounds in terms of complexity and ensures the safety of these bounds even for non-schedulable traffic. We provide further insights into the tightness and complexity issues of worst-case delay bounds yielded by the extended BATA with the Graph-based approach, denoted G-BATA. Our assessments show that the complexity has decreased by up to 100 times while offering an average tightness ratio of 71%, with reference to the basic BATA. Finally, we evaluate the yielded improvements with G-BATA for a realistic use case against a recent state-of-the-art approach. This evaluation shows the applicability of G-BATA under more general assumptions and the impact of such a feature on the tightness and computation time.
Designing Evaluations of Machine Learning Models for Subjective Inference: The Case of Sentence Toxicity
Venue: arXiv cs.LG 2019
Year: 2019

Machine Learning (ML) is increasingly applied in real-life scenarios, raising concerns about bias in automatic decision making. We focus on bias as a notion of opinion exclusion, that stems from the direct application of traditional ML pipelines to infer subjective properties. We argue that such ML systems should be evaluated with subjectivity and bias in mind. Considering the lack of evaluation standards yet to create evaluation benchmarks, we propose an initial list of specifications to define prior to creating evaluation datasets, in order to later accurately evaluate the biases. With the example of a sentence toxicity inference system, we illustrate how the specifications support the analysis of biases related to subjectivity. We highlight difficulties in instantiating these specifications and list future work for the crowdsourcing community to help the creation of appropriate evaluation datasets.
Algorithms and Adaptivity Gaps for Stochastic $k$-TSP
Venue: arXiv cs.DS 2019
Year: 2019

Given a metric $(V,d)$ and a $\textsf{root} \in V$, the classic $\textsf{$k$-TSP}$ problem is to find a tour originating at the $\textsf{root}$ of minimum length that visits at least $k$ nodes in $V$. In this work, motivated by applications where the input to an optimization problem is uncertain, we study two stochastic versions of $\textsf{$k$-TSP}$. In Stoch-Reward $k$-TSP, originally defined by Ene-Nagarajan-Saket [ENS17], each vertex $v$ in the given metric $(V,d)$ contains a stochastic reward $R_v$. The goal is to adaptively find a tour of minimum expected length that collects at least reward $k$; here "adaptively" means our next decision may depend on previous outcomes. Ene et al. give an $O(\log k)$-approximation adaptive algorithm for this problem, and left open if there is an $O(1)$-approximation algorithm. We totally resolve their open question and even give an $O(1)$-approximation \emph{non-adaptive} algorithm for this problem. We also introduce and obtain similar results for the Stoch-Cost $k$-TSP problem. In this problem each vertex $v$ has a stochastic cost $C_v$, and the goal is to visit and select at least $k$ vertices to minimize the expected \emph{sum} of tour length and cost of selected vertices. This problem generalizes the Price of Information framework [Singla18] from deterministic probing costs to metric probing costs. Our techniques are based on two crucial ideas: "repetitions" and "critical scaling". We show using Freedman's and Jogdeo-Samuels' inequalities that for our problems, if we truncate the random variables at an ideal threshold and repeat, then their expected values form a good surrogate. Unfortunately, this ideal threshold is adaptive as it depends on how far we are from achieving our target $k$, so we truncate at various different scales and identify a "critical" scale.
DC-S3GD: Delay-Compensated Stale-Synchronous SGD for Large-Scale Decentralized Neural Network Training
Venue: arXiv cs.LG 2019
Year: 2019

Data parallelism has become the de facto standard for training Deep Neural Network on multiple processing units. In this work we propose DC-S3GD, a decentralized (without Parameter Server) stale-synchronous version of the Delay-Compensated Asynchronous Stochastic Gradient Descent (DC-ASGD) algorithm. In our approach, we allow for the overlap of computation and communication, and compensate the inherent error with a first-order correction of the gradients. We prove the effectiveness of our approach by training Convolutional Neural Network with large batches and achieving state-of-the-art results.
Variety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory
Venue: arXiv cs.CC 2019
Year: 2019

We study the variety membership testing problem in the case when the variety is given as an orbit closure and the ambient space is the set of all 3-tensors. The first variety that we consider is the slice rank variety, which consists of all 3-tensors of slice rank at most $r$. We show that the membership testing problem for the slice rank variety is $\NP$-hard. While the slice rank variety is a union of orbit closures, we define another variety, the minrank variety, expressible as a single orbit closure. Our next result is the $\NP$-hardness of membership testing in the minrank variety, hence we establish the $\NP$-hardness of the orbit closure containment problem for 3-tensors. Algebraic natural proofs were recently introduced by Forbes, Shpilka and Volk and independently by Grochow, Kumar, Saks and Saraf. Bläser et al. gave a version of an algebraic natural proof barrier for the matrix completion problem which relies on $\coNP \subseteq \exists \BPP$. It implied that constructing equations for the corresponding variety should be hard. We generalize their approach to work with any family of varieties for which the membership problem is $\NP$-hard and for which we can efficiently generate a dense subset. Therefore, a similar barrier holds for the slice rank and the minrank varieties, too. This allows us to set up the slice rank and the minrank varieties as a test-bed for geometric complexity theory (GCT). We determine the stabilizers of the tensors that generate the orbit closures of the two varieties and prove that these tensors are almost characterized by their symmetries. We prove several nontrivial equations for both the varieties using different GCT methods. Many equations also work in the regime where membership testing in the slice rank or minrank varieties is $\NP$-hard. We view this as a promising sign that the GCT approach might indeed be successful.
SCL: Towards Accurate Domain Adaptive Object Detection via Gradient Detach Based Stacked Complementary Losses
Venue: arXiv cs.CV 2019
Year: 2019

Unsupervised domain adaptive object detection aims to learn a robust detector in the domain shift circumstance, where the training (source) domain is label-rich with bounding box annotations, while the testing (target) domain is label-agnostic and the feature distributions between training and testing domains are dissimilar or even totally different. In this paper, we propose a gradient detach based stacked complementary losses (SCL) method that uses detection losses as the primary objective, and cuts in several auxiliary losses in different network stages accompanying with gradient detach training to learn more discriminative representations. We argue that the prior methods mainly leverage more loss functions for training but ignore the interaction of different losses and also the compatible training strategy (gradient detach updating in our work). Thus, our proposed method is a more syncretic adaptation learning process. We conduct comprehensive experiments on seven datasets, the results demonstrate that our method performs favorably better than the state-of-the-art methods by a significant margin. For instance, from Cityscapes to FoggyCityscapes, we achieve 37.9% mAP, outperforming the previous art Strong-Weak by 3.6%.
Hyper-SAGNN: a self-attention based graph neural network for hypergraphs
Venue: arXiv cs.LG 2019
Year: 2019

Graph representation learning for hypergraphs can be used to extract patterns among higher-order interactions that are critically important in many real world problems. Current approaches designed for hypergraphs, however, are unable to handle different types of hypergraphs and are typically not generic for various learning tasks. Indeed, models that can predict variable-sized heterogeneous hyperedges have not been available. Here we develop a new self-attention based graph neural network called Hyper-SAGNN applicable to homogeneous and heterogeneous hypergraphs with variable hyperedge sizes. We perform extensive evaluations on multiple datasets, including four benchmark network datasets and two single-cell Hi-C datasets in genomics. We demonstrate that Hyper-SAGNN significantly outperforms the state-of-the-art methods on traditional tasks while also achieving great performance on a new task called outsider identification. Hyper-SAGNN will be useful for graph representation learning to uncover complex higher-order interactions in different applications.
Data Generation for Neural Programming by Example
Venue: arXiv cs.LG 2019
Year: 2019

Programming by example is the problem of synthesizing a program from a small set of input / output pairs. Recent works applying machine learning methods to this task show promise, but are typically reliant on generating synthetic examples for training. A particular challenge lies in generating meaningful sets of inputs and outputs, which well-characterize a given program and accurately demonstrate its behavior. Where examples used for testing are generated by the same method as training data then the performance of a model may be partly reliant on this similarity. In this paper we introduce a novel approach using an SMT solver to synthesize inputs which cover a diverse set of behaviors for a given program. We carry out a case study comparing this method to existing synthetic data generation procedures in the literature, and find that data generated using our approach improves both the discriminatory power of example sets and the ability of trained machine learning models to generalize to unfamiliar data.
Homo Cyberneticus: The Era of Human-AI Integration
Venue: arXiv cs.HC 2019
Year: 2019

This article is submitted and accepted as ACM UIST 2019 Visions. UIST Visions is a venue for forward thinking ideas to inspire the community. The goal is not to report research but to project and propose new research directions. This article, entitled "Homo Cyberneticus: The Era of Human-AI Integration", proposes HCI research directions, namely human-augmentation and human-AI-integration.
Certain Answers to a SPARQL Query over a Knowledge Base (extended version)
Venue: arXiv cs.DB 2019
Year: 2019

Ontology-Mediated Query Answering (OMQA) is a well-established framework to answer queries over an RDFS or OWL Knowledge Base (KB). OMQA was originally designed for unions of conjunctive queries (UCQs), and based on certain answers. More recently, OMQA has been extended to SPARQL queries, but to our knowledge, none of the efforts made in this direction (either in the literature, or the so-called SPARQL entailment regimes) is able to capture both certain answers for UCQs and the standard interpretation of SPARQL over a plain graph. We formalize these as requirements to be met by any semantics aiming at conciliating certain answers and SPARQL answers, and define three additional requirements, which generalize to KBs some basic properties of SPARQL answers. Then we show that a semantics can be defined that satisfies all requirements for SPARQL queries with SELECT, UNION, and OPTIONAL, and for DLs with the canonical model property. We also investigate combined complexity for query answering under such a semantics over DL-Lite R KBs. In particular, we show for different fragments of SPARQL that known upper-bounds for query answering over a plain graph are matched.
Physics-Guided Architecture (PGA) of Neural Networks for Quantifying Uncertainty in Lake Temperature Modeling
Venue: arXiv cs.LG 2019
Year: 2019

To simultaneously address the rising need of expressing uncertainties in deep learning models along with producing model outputs which are consistent with the known scientific knowledge, we propose a novel physics-guided architecture (PGA) of neural networks in the context of lake temperature modeling where the physical constraints are hard coded in the neural network architecture. This allows us to integrate such models with state of the art uncertainty estimation approaches such as Monte Carlo (MC) Dropout without sacrificing the physical consistency of our results. We demonstrate the effectiveness of our approach in ensuring better generalizability as well as physical consistency in MC estimates over data collected from Lake Mendota in Wisconsin and Falling Creek Reservoir in Virginia, even with limited training data. We further show that our MC estimates correctly match the distribution of ground-truth observations, thus making the PGA paradigm amenable to physically grounded uncertainty quantification.
Sparse Coding on Cascaded Residuals
Venue: arXiv cs.CV 2019
Year: 2019

This paper seeks to combine dictionary learning and hierarchical image representation in a principled way. To make dictionary atoms capturing additional information from extended receptive fields and attain improved descriptive capacity, we present a two-pass multi-resolution cascade framework for dictionary learning and sparse coding. The cascade allows collaborative reconstructions at different resolutions using the same dimensional dictionary atoms. Our jointly learned dictionary comprises atoms that adapt to the information available at the coarsest layer where the support of atoms reaches their maximum range and the residual images where the supplementary details progressively refine the reconstruction objective. The residual at a layer is computed by the difference between the aggregated reconstructions of the previous layers and the downsampled original image at that layer. Our method generates more flexible and accurate representations using much less number of coefficients. Its computational efficiency stems from encoding at the coarsest resolution, which is minuscule, and encoding the residuals, which are relatively much sparse. Our extensive experiments on multiple datasets demonstrate that this new method is powerful in image coding, denoising, inpainting and artifact removal tasks outperforming the state-of-the-art techniques.
Sequence-Aware Factorization Machines for Temporal Predictive Analytics
Venue: arXiv cs.LG 2019
Year: 2019

In various web applications like targeted advertising and recommender systems, the available categorical features (e.g., product type) are often of great importance but sparse. As a widely adopted solution, models based on Factorization Machines (FMs) are capable of modelling high-order interactions among features for effective sparse predictive analytics. As the volume of web-scale data grows exponentially over time, sparse predictive analytics inevitably involves dynamic and sequential features. However, existing FM-based models assume no temporal orders in the data, and are unable to capture the sequential dependencies or patterns within the dynamic features, impeding the performance and adaptivity of these methods. Hence, in this paper, we propose a novel Sequence-Aware Factorization Machine (SeqFM) for temporal predictive analytics, which models feature interactions by fully investigating the effect of sequential dependencies. As static features (e.g., user gender) and dynamic features (e.g., user interacted items) express different semantics, we innovatively devise a multi-view self-attention scheme that separately models the effect of static features, dynamic features and the mutual interactions between static and dynamic features in three different views. In SeqFM, we further map the learned representations of feature interactions to the desired output with a shared residual network. To showcase the versatility and generalizability of SeqFM, we test SeqFM in three popular application scenarios for FM-based models, namely ranking, classification and regression tasks. Extensive experimental results on six large-scale datasets demonstrate the superior effectiveness and efficiency of SeqFM.
Characterizing behavioral trends in a community driven discussion platform
Venue: arXiv cs.SI 2019
Year: 2019

This article presents a systematic analysis of the patterns of behavior of individuals as well as groups observed in community-driven platforms for discussion like Reddit, where users usually exchange information and viewpoints on their topics of interest. We perform a statistical analysis of the behavior of posts and model the users' interactions around them. A platform like Reddit which has grown exponentially, starting from a very small community to one of the largest social networks, with its large user base and popularity harboring a variety of behavior of users in terms of their activity. Our work provides interesting insights about a huge number of inactive posts which fail to attract attention despite their authors exhibiting Cyborg-like behavior to attract attention. We also observe short-lived yet extremely active posts emulate a phenomenon like Mayfly Buzz. A method is presented, to study the activity around posts which are highly active, to determine the presence of Limelight hogging activity. We also present a systematic analysis to study the presence of controversies in posts. We analyzed data from two periods of one-year duration but separated by few years in time, to understand how social media has evolved through the years.