OpenRaiser/Intern-Atlas huggingface dataset:
Random Sum-Product Forests with Residual Links
Venue: arXiv cs.LG 2019
Year: 2019

Tractable yet expressive density estimators are a key building block of probabilistic machine learning. While sum-product networks (SPNs) offer attractive inference capabilities, obtaining structures large enough to fit complex, high-dimensional data has proven challenging. In this paper, we present random sum-product forests (RSPFs), an ensemble approach for mixing multiple randomly generated SPNs. We also introduce residual links, which reference specialized substructures of other component SPNs in order to leverage the context-specific knowledge encoded within them. Our empirical evidence demonstrates that RSPFs provide better performance than their individual components. Adding residual links improves the models further, allowing the resulting ResSPNs to be competitive with commonly used structure learning methods.
On Symbolic Approaches for Computing the Matrix Permanent
Venue: arXiv cs.DS 2019
Year: 2019

Counting the number of perfect matchings in bipartite graphs, or equivalently computing the permanent of 0-1 matrices, is an important combinatorial problem that has been extensively studied by theoreticians and practitioners alike. The permanent is #P-Complete; hence it is unlikely that a polynomial-time algorithm exists for the problem. Researchers have therefore focused on finding tractable subclasses of matrices for permanent computation. One such subclass that has received much attention is that of sparse matrices i.e. matrices with few entries set to 1, the rest being 0. For this subclass, improved theoretical upper bounds and practically efficient algorithms have been developed. In this paper, we ask whether it is possible to go beyond sparse matrices in our quest for developing scalable techniques for the permanent, and answer this question affirmatively. Our key insight is to represent permanent computation symbolically using Algebraic Decision Diagrams (ADDs). ADD-based techniques naturally use dynamic programming, and hence avoid redundant computation through memoization. This permits exploiting the hidden structure in a large class of matrices that have so far remained beyond the reach of permanent computation techniques. The availability of sophisticated libraries implementing ADDs also makes the task of engineering practical solutions relatively straightforward. While a complete characterization of matrices admitting a compact ADD representation remains open, we provide strong experimental evidence of the effectiveness of our approach for computing the permanent, not just for sparse matrices, but also for dense matrices and for matrices with "similar" rows.
De-anonymization Attacks on Neuroimaging Datasets
Venue: arXiv cs.CR 2019
Year: 2019

Advances in imaging technologies, combined with inexpensive storage, have led to an explosion in the volume of publicly available neuroimaging datasets. Effective analyses of these images hold the potential for uncovering mechanisms that govern functioning of the human brain, and understanding various neurological diseases and disorders. The potential significance of these studies notwithstanding, a growing concern relates to the protection of privacy and confidentiality of subjects who participate in these studies. In this paper, we present a de-anonymization attack rooted in the innate uniqueness of the structure and function of the human brain. We show that the attack reveals not only the identity of an individual, but also the task they are performing, and their efficacy in performing the tasks. Our attack relies on novel matrix analyses techniques that are used to extract discriminating features in neuroimages. These features correspond to individual-specific signatures that can be matched across datasets to yield highly accurate identification. We present data preprocessing, signature extraction, and matching techniques that are computationally inexpensive, and can scale to large datasets. We discuss implications of the attack and challenges associated with defending against such attacks.
Using Semantic Role Knowledge for Relevance Ranking of Key Phrases in Documents: An Unsupervised Approach
Venue: arXiv cs.IR 2019
Year: 2019

In this paper, we investigate the integration of sentence position and semantic role of words in a PageRank system to build a key phrase ranking method. We present the evaluation results of our approach on three scientific articles. We show that semantic role information, when integrated with a PageRank system, can become a new lexical feature. Our approach had an overall improvement on all the data sets over the state-of-art baseline approaches.
Fully Convolutional Search Heuristic Learning for Rapid Path Planners
Venue: arXiv cs.LG 2019
Year: 2019

Path-planning algorithms are an important part of a wide variety of robotic applications, such as mobile robot navigation and robot arm manipulation. However, in large search spaces in which local traps may exist, it remains challenging to reliably find a path while satisfying real-time constraints. Efforts to speed up the path search have led to the development of many practical path-planning algorithms. These algorithms often define a search heuristic to guide the search towards the goal. The heuristics should be carefully designed for each specific problem to ensure reliability in the various situations encountered in the problem. However, it is often difficult for humans to craft such robust heuristics, and the search performance often degrades under conditions that violate the heuristic assumption. Rather than manually designing the heuristics, in this work, we propose a learning approach to acquire these search heuristics. Our method represents the environment containing the obstacles as an image, and this image is fed into fully convolutional neural networks to produce a search heuristic image where every pixel represents a heuristic value (cost-to-go value to a goal) in the form of a vertex of a search graph. Training the heuristic is performed using previously collected planning results. Our preliminary experiments (2D grid world navigation experiments) demonstrate significant reduction in the search costs relative to a hand-designed heuristic.
Decision Making with Argumentation Graphs
Venue: arXiv cs.CY 2019
Year: 2019

This work is about making decisions by digital means. Funds should be distributed by the students of Heinrich-Heine-University. The proposals were made by the students themselves without further influence. For this purpose, dialog-based argumentation is used to give the participants a better understanding of various arguments. In addition, a software service has been developed which allows the students to express their preferences for various proposals. An experiment was carried out at the university, which should prove whether students are satisfied with this type of participation. The results indicate that the procedure is well accepted and thus successful. However, improvements to the process itself were necessary during the experiment and should be considered for future procedures. Further procedures are desired.
MakeSense: An IoT Testbed for Social Research of Indoor Activities
Venue: arXiv cs.HC 2019
Year: 2019

There has been increasing interest in deploying IoT devices to study human behaviour in locations such as homes and offices. Such devices can be deployed in a laboratory or `in the wild' in natural environments. The latter allows one to collect behavioural data that is not contaminated by the artificiality of a laboratory experiment. Using IoT devices in ordinary environments also brings the benefits of reduced cost, as compared with lab experiments, and less disturbance to the participants' daily routines which in turn helps with recruiting them into the research. However, in this case, it is essential to have an IoT infrastructure that can be easily and swiftly installed and from which real-time data can be securely and straightforwardly collected. In this paper, we present MakeSense, an IoT testbed that enables real-world experimentation for large scale social research on indoor activities through real-time monitoring and/or situation-aware applications. The testbed features quick setup, flexibility in deployment, the integration of a range of IoT devices, resilience, and scalability. We also present two case studies to demonstrate the use of the testbed, one in homes and one in offices.
Advanced profiling for probabilistic Prime+Probe attacks and covert channels in ScatterCache
Venue: arXiv cs.CR 2019
Year: 2019

Timing channels in cache hierarchies are an important enabler in many microarchitectural attacks. ScatterCache (USENIX 2019) is a protected cache architecture that randomizes the address-to-index mapping with a keyed cryptographic function, aiming to thwart the usage of cache-based timing channels in microarchitectural attacks. In this note, we advance the understanding of the security of ScatterCache by outlining two attacks in the noise-free case, i.e. matching the assumptions in the original analysis. As a first contribution, we present more efficient eviction set profiling, reducing the required number of observable victim accesses (and hence profiling runtime) by several orders of magnitude. For instance, to construct a reliable eviction set in an 8-way set associative cache with 11 index bits, we relax victim access requirements from approximately $2^{25}$ to less than $2^{10}$ . As a second contribution, we demonstrate covert channel profiling and transmission in probabilistic caches like ScatterCache. By exploiting arbitrary collisions instead of targeted ones, our approach significantly outperforms known covert channels (e.g. full-cache eviction).
No Need of Data Pre-processing: A General Framework for Radio-Based Device-Free Context Awareness
Venue: arXiv cs.NI 2019
Year: 2019

Device-free context awareness is important to many applications. There are two broadly used approaches for device-free context awareness, i.e. video-based and radio-based. Video-based applications can deliver good performance, but privacy is a serious concern. Radio-based context awareness has drawn researchers attention instead because it does not violate privacy and radio signal can penetrate obstacles. Recently, deep learning has been introduced into radio-based device-free context awareness and helps boost the recognition accuracy. The present works design explicit methods for each radio based application. They also use one additional step to extract features before conducting classification and exploit deep learning as a classification tool. The additional initial data processing step introduces unnecessary noise and information loss. Without initial data processing, it is, however, challenging to explore patterns of raw signals. In this paper, we are the first to propose an innovative deep learning based general framework for both signal processing and classification. The key novelty of this paper is that the framework can be generalised for all the radio-based context awareness applications. We also eliminate the additional effort to extract features from raw radio signals. We conduct extensive evaluations to show the superior performance of our proposed method and its generalisation.
Probabilistic Models with Deep Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

Recent advances in statistical inference have significantly expanded the toolbox of probabilistic modeling. Historically, probabilistic modeling has been constrained to (i) very restricted model classes where exact or approximate probabilistic inference were feasible, and (ii) small or medium-sized data sets which fit within the main memory of the computer. However, developments in variational inference, a general form of approximate probabilistic inference originated in statistical physics, are allowing probabilistic modeling to overcome these restrictions: (i) Approximate probabilistic inference is now possible over a broad class of probabilistic models containing a large number of parameters, and (ii) scalable inference methods based on stochastic gradient descent and distributed computation engines allow to apply probabilistic modeling over massive data sets. One important practical consequence of these advances is the possibility to include deep neural networks within a probabilistic model to capture complex non-linear stochastic relationships between random variables. These advances in conjunction with the release of novel probabilistic modeling toolboxes have greatly expanded the scope of application of probabilistic models, and allow these models to take advantage of the recent strides made by the deep learning community. In this paper we review the main concepts, methods and tools needed to use deep neural networks within a probabilistic modeling framework.
Privacy-Aware Distributed Mobility Choice Modelling over Blockchain
Venue: arXiv cs.CR 2019
Year: 2019

A generalized distributed tool for mobility choice modelling is presented, where participants do not share personal raw data, while all computations are done locally. Participants use Blockchain based Smart Mobility Data-market (BSMD), where all transactions are secure and private. Nodes in blockchain can transact information with other participants as long as both parties agree to the transaction rules issued by the owner of the data. A case study is presented where a mode choice model is distributed and estimated over BSMD. As an example, the parameter estimation problem is solved on a distributed version of simulated annealing. It is demonstrated that the estimated model parameters are consistent and reproducible.
BERT-based Ranking for Biomedical Entity Normalization
Venue: arXiv cs.IR 2019
Year: 2019

Developing high-performance entity normalization algorithms that can alleviate the term variation problem is of great interest to the biomedical community. Although deep learning-based methods have been successfully applied to biomedical entity normalization, they often depend on traditional context-independent word embeddings. Bidirectional Encoder Representations from Transformers (BERT), BERT for Biomedical Text Mining (BioBERT) and BERT for Clinical Text Mining (ClinicalBERT) were recently introduced to pre-train contextualized word representation models using bidirectional Transformers, advancing the state-of-the-art for many natural language processing tasks. In this study, we proposed an entity normalization architecture by fine-tuning the pre-trained BERT / BioBERT / ClinicalBERT models and conducted extensive experiments to evaluate the effectiveness of the pre-trained models for biomedical entity normalization using three different types of datasets. Our experimental results show that the best fine-tuned models consistently outperformed previous methods and advanced the state-of-the-art for biomedical entity normalization, with up to 1.17% increase in accuracy.
Reordering Derivatives of Trace Closures of Regular Languages (Full Version)
Venue: arXiv cs.FL 2019
Year: 2019

We provide syntactic derivative-like operations, defined by recursion on regular expressions, in the styles of both Brzozowski and Antimirov, for trace closures of regular languages. Just as the Brzozowski and Antimirov derivative operations for regular languages, these syntactic reordering derivative operations yield deterministic and nondeterministic automata respectively. But trace closures of regular languages are in general not regular, hence these automata cannot generally be finite. Still, as we show, for star-connected expressions, the Antimirov and Brzozowski automata, suitably quotiented, are finite. We also define a refined version of the Antimirov reordering derivative operation where parts-of-derivatives (states of the automaton) are nonempty lists of regular expressions rather than single regular expressions. We define the uniform scattering rank of a language and show that, for a regexp whose language has finite uniform scattering rank, the truncation of the (generally infinite) refined Antimirov automaton, obtained by removing long states, is finite without any quotienting, but still accepts the trace closure. We also show that star-connected languages have finite uniform scattering rank.
VisualBERT: A Simple and Performant Baseline for Vision and Language
Venue: arXiv cs.CV 2019
Year: 2019

We propose VisualBERT, a simple and flexible framework for modeling a broad range of vision-and-language tasks. VisualBERT consists of a stack of Transformer layers that implicitly align elements of an input text and regions in an associated input image with self-attention. We further propose two visually-grounded language model objectives for pre-training VisualBERT on image caption data. Experiments on four vision-and-language tasks including VQA, VCR, NLVR2, and Flickr30K show that VisualBERT outperforms or rivals with state-of-the-art models while being significantly simpler. Further analysis demonstrates that VisualBERT can ground elements of language to image regions without any explicit supervision and is even sensitive to syntactic relationships, tracking, for example, associations between verbs and image regions corresponding to their arguments.
Transferring knowledge from monitored to unmonitored areas for forecasting parking spaces
Venue: arXiv cs.LG 2019
Year: 2019

Smart cities around the world have begun monitoring parking areas in order to estimate available parking spots and help drivers looking for parking. The current results are promising, indeed. However, existing approaches are limited by the high cost of sensors that need to be installed throughout the city in order to achieve an accurate estimation. This work investigates the extension of estimating parking information from areas equipped with sensors to areas where they are missing. To this end, the similarity between city neighborhoods is determined based on background data, i.e., from geographic information systems. Using the derived similarity values, we analyze the adaptation of occupancy rates from monitored- to unmonitored parking areas.
Performance of Devito on HPC-Optimised ARM Processors
Venue: arXiv cs.PF 2019
Year: 2019

We evaluate the performance of Devito, a domain specific language (DSL) for finite differences on Arm ThunderX2 processors. Experiments with two common seismic computational kernels demonstrate that Arm processors can deliver competitive performance compared to other Intel Xeon processors.
SCAR: Spatial-/Channel-wise Attention Regression Networks for Crowd Counting
Venue: arXiv cs.CV 2019
Year: 2019

Recently, crowd counting is a hot topic in crowd analysis. Many CNN-based counting algorithms attain good performance. However, these methods only focus on the local appearance features of crowd scenes but ignore the large-range pixel-wise contextual and crowd attention information. To remedy the above problems, in this paper, we introduce the Spatial-/Channel-wise Attention Models into the traditional Regression CNN to estimate the density map, which is named as "SCAR". It consists of two modules, namely Spatial-wise Attention Model (SAM) and Channel-wise Attention Model (CAM). The former can encode the pixel-wise context of the entire image to more accurately predict density maps at the pixel level. The latter attempts to extract more discriminative features among different channels, which aids model to pay attention to the head region, the core of crowd scenes. Intuitively, CAM alleviates the mistaken estimation for background regions. Finally, two types of attention information and traditional CNN's feature maps are integrated by a concatenation operation. Furthermore, the extensive experiments are conducted on four popular datasets, Shanghai Tech Part A/B, GCC, and UCF_CC_50 Dataset. The results show that the proposed method achieves state-of-the-art results.
Introduction to the 35th International Conference on Logic Programming Special Issue
Venue: arXiv cs.LO 2019
Year: 2019

We are proud to introduce this special issue of Theory and Practice of Logic Programming (TPLP), dedicated to the regular papers accepted for the 35th International Conference on Logic Programming (ICLP). The ICLP meetings started in Marseille in 1982 and since then constitute the main venue for presenting and discussing work in the area of logic programming. Under consideration for acceptance in TPLP.
Modeling Graphs with Vertex Replacement Grammars
Venue: arXiv cs.SI 2019
Year: 2019

One of the principal goals of graph modeling is to capture the building blocks of network data in order to study various physical and natural phenomena. Recent work at the intersection of formal language theory and graph theory has explored the use of graph grammars for graph modeling. However, existing graph grammar formalisms, like Hyperedge Replacement Grammars, can only operate on small tree-like graphs. The present work relaxes this restriction by revising a different graph grammar formalism called Vertex Replacement Grammars (VRGs). We show that a variant of the VRG called Clustering-based Node Replacement Grammar (CNRG) can be efficiently extracted from many hierarchical clusterings of a graph. We show that CNRGs encode a succinct model of the graph, yet faithfully preserves the structure of the original graph. In experiments on large real-world datasets, we show that graphs generated from the CNRG model exhibit a diverse range of properties that are similar to those found in the original networks.
Graph Motif Problems Parameterized by Dual
Venue: arXiv cs.CC 2019
Year: 2019

Let $G=(V,E)$ be a vertex-colored graph, where $C$ is the set of colors used to color $V$. The Graph Motif (or GM) problem takes as input $G$, a multiset $M$ of colors built from $C$, and asks whether there is a subset $S\subseteq V$ such that (i) $G[S]$ is connected and (ii) the multiset of colors obtained from $S$ equals $M$. The Colorful Graph Motif (or CGM) problem is the special case of GM in which $M$ is a set, and the List-Colored Graph Motif (or LGM) problem is the extension of GM in which each vertex $v$ of $V$ may choose its color from a list $\mathcal{L}(v)\subseteq C$ of colors. We study the three problems GM, CGM, and LGM, parameterized by the dual parameter $\ell:=|V|-|M|$. For general graphs, we show that, assuming the strong exponential time hypothesis, CGM has no $(2-ε)^\ell\cdot |V|^{\mathcal{O}(1)}$-time algorithm, which implies that a previous algorithm, running in $\mathcal{O}(2^\ell\cdot |E|)$ time is optimal [Betzler et al., IEEE/ACM TCBB 2011]. We also prove that LGM is W[1]-hard with respect to $\ell$ even if we restrict ourselves to lists of at most two colors. If we constrain the input graph to be a tree, then we show that GM can be solved in $\mathcal{O}(3^\ell\cdot |V|)$ time but admits no polynomial-size problem kernel, while CGM can be solved in $\mathcal{O}(\sqrt{2}^{\ell} + |V|)$ time and admits a polynomial-size problem kernel.