OpenRaiser/Intern-Atlas huggingface dataset:
From Low-Level Events to Activities -- A Session-Based Approach (Extended Version)
Venue: arXiv cs.AI 2019
Year: 2019

Process-Mining techniques aim to use event data about past executions to gain insight into how processes are executed. While these techniques are proven to be very valuable, they are less successful to reach their goal if the process is flexible and, hence, events can potentially occur in any order. Furthermore, information systems can record events at very low level, which do not match the high-level concepts known at business level. Without abstracting sequences of events to high-level concepts, the results of applying process mining (e.g., discovered models) easily become very complex and difficult to interpret, which ultimately means that they are of little use. A large body of research exists on event abstraction but typically a large amount of domain knowledge is required to be fed in, which is often not readily available. Other abstraction techniques are unsupervised, which give lower accuracy. This paper puts forward a technique that requires limited domain knowledge that can be easily provided. Traces are divided in sessions, and each session is abstracted as one single high-level activity execution. The abstraction is based on a combination of automatic clustering and visualization methods. The technique was assessed on two case studies that evidently exhibits a large amount of behavior. The results clearly illustrate the benefits of the abstraction to convey knowledge to stakeholders.
Optimal Collusion-Free Teaching
Venue: arXiv cs.LG 2019
Year: 2019

Formal models of learning from teachers need to respect certain criteria to avoid collusion. The most commonly accepted notion of collusion-freeness was proposed by Goldman and Mathias (1996), and various teaching models obeying their criterion have been studied. For each model $M$ and each concept class $\mathcal{C}$, a parameter $M$-$\mathrm{TD}(\mathcal{C})$ refers to the teaching dimension of concept class $\mathcal{C}$ in model $M$---defined to be the number of examples required for teaching a concept, in the worst case over all concepts in $\mathcal{C}$. This paper introduces a new model of teaching, called no-clash teaching, together with the corresponding parameter $\mathrm{NCTD}(\mathcal{C})$. No-clash teaching is provably optimal in the strong sense that, given any concept class $\mathcal{C}$ and any model $M$ obeying Goldman and Mathias's collusion-freeness criterion, one obtains $\mathrm{NCTD}(\mathcal{C})\le M$-$\mathrm{TD}(\mathcal{C})$. We also study a corresponding notion $\mathrm{NCTD}^+$ for the case of learning from positive data only, establish useful bounds on $\mathrm{NCTD}$ and $\mathrm{NCTD}^+$, and discuss relations of these parameters to the VC-dimension and to sample compression. In addition to formulating an optimal model of collusion-free teaching, our main results are on the computational complexity of deciding whether $\mathrm{NCTD}^+(\mathcal{C})=k$ (or $\mathrm{NCTD}(\mathcal{C})=k$) for given $\mathcal{C}$ and $k$. We show some such decision problems to be equivalent to the existence question for certain constrained matchings in bipartite graphs. Our NP-hardness results for the latter are of independent interest in the study of constrained graph matchings.
Asymptotically faster algorithm for counting self-avoiding walks and self-avoiding polygons
Venue: arXiv cs.DS 2019
Year: 2019

We give an algorithm for counting self-avoiding walks or self-avoiding polygons that runs in time $\exp(C\sqrt{n\log n})$ on 2-dimensional lattices and time $\exp(C_dn^{(d-1)/d}\log n)$ on $d$-dimensional lattices for $d>2$.
On Separable Quadratic Lyapunov Functions for Convex Design of Distributed Controllers
Venue: arXiv cs.SY 2019
Year: 2019

We consider the problem of designing a stabilizing and optimal static controller with a pre-specified sparsity pattern. Since this problem is NP-hard in general, it is necessary to resort to approximation approaches. In this paper, we characterize a class of convex restrictions of this problem that are based on designing a separable quadratic Lyapunov function for the closed-loop system. This approach generalizes previous results based on optimizing over diagonal Lyapunov functions, thus allowing for improved feasibility and performance. Moreover, we suggest a simple procedure to compute favourable structures for the Lyapunov function yielding high-performance distributed controllers. Numerical examples validate our results.
Instance- and Category-level 6D Object Pose Estimation
Venue: arXiv cs.CV 2019
Year: 2019

6D object pose estimation is an important task that determines the 3D position and 3D rotation of an object in camera-centred coordinates. By utilizing such a task, one can propose promising solutions for various problems related to scene understanding, augmented reality, control and navigation of robotics. Recent developments on visual depth sensors and low-cost availability of depth data significantly facilitate object pose estimation. Using depth information from RGB-D sensors, substantial progress has been made in the last decade by the methods addressing the challenges such as viewpoint variability, occlusion and clutter, and similar looking distractors. Particularly, with the recent advent of convolutional neural networks, RGB-only based solutions have been presented. However, improved results have only been reported for recovering the pose of known instances, i.e., for the instance-level object pose estimation tasks. More recently, state-of-the-art approaches target to solve object pose estimation problem at the level of categories, recovering the 6D pose of unknown instances. To this end, they address the challenges of the category-level tasks such as distribution shift among source and target domains, high intra-class variations, and shape discrepancies between objects.
CloudSafe: A Tool for an Automated Security Analysis for Cloud Computing
Venue: arXiv cs.CR 2019
Year: 2019

Cloud computing has been adopted widely, providing on-demand computing resources to improve perfornance and reduce the operational costs. However, these new functionalities also bring new ways to exploit the cloud computing environment. To assess the security of the cloud, graphical security models can be used, such as Attack Graphs and Attack Trees. However, existing models do not consider all types of threats, and also automating the security assessment functions are difficult. In this paper, we propose a new security assessment tool for the cloud named CloudSafe, an automated security assessment for the cloud. The CloudSafe tool collates various tools and frameworks to automate the security assessment process. To demonstrate the applicability of the CloudSafe, we conducted security assessment in Amazon AWS, where our experimental results showed that we can effectively gather security information of the cloud and carry out security assessment to produce security reports. Users and cloud service providers can use the security report generated by the CloudSafe to understand the security posture of the cloud being used/provided.
A Clustering-Based Combinatorial Approach to Unsupervised Matching of Product Titles
Venue: arXiv cs.IR 2019
Year: 2019

The constant growth of the e-commerce industry has rendered the problem of product retrieval particularly important. As more enterprises move their activities on the Web, the volume and the diversity of the product-related information increase quickly. These factors make it difficult for the users to identify and compare the features of their desired products. Recent studies proved that the standard similarity metrics cannot effectively identify identical products, since similar titles often refer to different products and vice-versa. Other studies employed external data sources (search engines) to enrich the titles; these solutions are rather impractical mainly because the external data fetching is slow. In this paper we introduce UPM, an unsupervised algorithm for matching products by their titles. UPM is independent of any external sources, since it analyzes the titles and extracts combinations of words out of them. These combinations are evaluated according to several criteria, and the most appropriate of them constitutes the cluster where a product is classified into. UPM is also parameter-free, it avoids product pairwise comparisons, and includes a post-processing verification stage which corrects the erroneous matches. The experimental evaluation of UPM demonstrated its superiority against the state-of-the-art approaches in terms of both efficiency and effectiveness.
An efficient iterative method for looped pipe network hydraulics
Venue: arXiv cs.CE 2019
Year: 2019

Original and improved version of the Hardy Cross iterative method with related modifications are today widely used for calculation of fluid flow through conduits in loops-like distribution networks of pipes with known node fluid consumptions. Fluid in these networks is usually natural gas for distribution in the municipalities, water in waterworks or hot water in district heating system, air in the case of ventilation systems in buildings or mines, etc. Since, the resistances in these networks depend of flow, problem is not linear like in electrical circuits, and iterative procedure must be used. In both version of the Hardy Cross method, in original and in the improved one, initial results of calculation in iteration procedure is not flow, but rather the correction of flow. Unfortunately, these corrections should be added to or subtracted from a flow calculated in previous iteration according to complicate algebraic rules. After the here presented node-loop method, final results in each of the iterations is flow directly rather than flow correction. In that way complex algebraic scheme for sign of flow correction is avoided, while the final results still remain unchanged. Numbers of required iterations for the same results are comparable with the improved Hardy Cross method.
Deep Recurrent Q-Learning vs Deep Q-Learning on a simple Partially Observable Markov Decision Process with Minecraft
Venue: arXiv cs.LG 2019
Year: 2019

Deep Q-Learning has been successfully applied to a wide variety of tasks in the past several years. However, the architecture of the vanilla Deep Q-Network is not suited to deal with partially observable environments such as 3D video games. For this, recurrent layers have been added to the Deep Q-Network in order to allow it to handle past dependencies. We here use Minecraft for its customization advantages and design two very simple missions that can be frames as Partially Observable Markov Decision Process. We compare on these missions the Deep Q-Network and the Deep Recurrent Q-Network in order to see if the latter, which is trickier and longer to train, is always the best architecture when the agent has to deal with partial observability.
Solving the minimum labeling global cut problem by mathematical programming
Venue: arXiv cs.DM 2019
Year: 2019

Let G = (V, E, L) be an edge-labeled graph such that V is the set of vertices, E is the set of edges, L is the set of labels (colors) and each edge e \in E has a label l(e) associated; The goal of the minimum labeling global cut problem (MLGCP) is to find a subset L \subseteq L of labels such that G = (V, E , LŁ) is not connected and |L| is minimized. This work proposes three new mathematical formulations for the MLGCP as well as branch-and-cut algorithms to solve them. The computational experiments showed that the proposed methods are able to solve small to average sized instances in a reasonable amount of time.
Model Checking ATL* on vCGS
Venue: arXiv cs.LO 2019
Year: 2019

We prove that the model checking ATL* on concurrent game structures with propositional control for atom-visibility (vCGS) is undecidable. To do so, we reduce this problem to model checking ATL* on iCGS.
ADS-ME: Anomaly Detection System for Micro-expression Spotting
Venue: arXiv cs.CV 2019
Year: 2019

Micro-expressions (MEs) are infrequent and uncontrollable facial events that can highlight emotional deception and appear in a high-stakes environment. This paper propose an algorithm for spatiotemporal MEs spotting. Since MEs are unusual events, we treat them as abnormal patterns that diverge from expected Normal Facial Behaviour (NFBs) patterns. NFBs correspond to facial muscle activations, eye blink/gaze events and mouth opening/closing movements that are all facial deformation but not MEs. We propose a probabilistic model to estimate the probability density function that models the spatiotemporal distributions of NFBs patterns. To rank the outputs, we compute the negative log-likelihood and we developed an adaptive thresholding technique to identify MEs from NFBs. While working only with NFBs data, the main challenge is to capture intrinsic spatiotemoral features, hence we design a recurrent convolutional autoencoder for feature representation. Finally, we show that our system is superior to previous works for MEs spotting.
Solving the Black Box Problem: A Normative Framework for Explainable Artificial Intelligence
Venue: arXiv cs.GL 2019
Year: 2019

Many of the computing systems programmed using Machine Learning are opaque: it is difficult to know why they do what they do or how they work. The Explainable Artificial Intelligence research program aims to develop analytic techniques with which to render opaque computing systems transparent, but lacks a normative framework with which to evaluate these techniques' explanatory success. The aim of the present discussion is to develop such a framework, while paying particular attention to different stakeholders' distinct explanatory requirements. Building on an analysis of 'opacity' from philosophy of science, this framework is modeled after David Marr's influential account of explanation in cognitive science. Thus, the framework distinguishes between the different questions that might be asked about an opaque computing system, and specifies the general way in which these questions should be answered. By applying this normative framework to current techniques such as input heatmapping, feature-detector identification, and diagnostic classification, it will be possible to determine whether and to what extent the Black Box Problem can be solved.
A Hybrid Controller for Obstacle Avoidance in an n-dimensional Euclidean Space
Venue: arXiv cs.SY 2019
Year: 2019

For a vehicle moving in an $n$-dimensional Euclidean space, we present a construction of a hybrid feedback that guarantees both global asymptotic stabilization of a reference position and avoidance of an obstacle corresponding to a bounded spherical region. The proposed hybrid control algorithm switches between two modes of operation: stabilization (motion-to-goal) and avoidance (boundary-following). The geometric construction of the flow and jump sets of the hybrid controller, exploiting a hysteresis region, guarantees robust switching (chattering-free) between the stabilization and avoidance modes. Simulation results illustrate the performance of the proposed hybrid control approach for a 3-dimensional scenario.
LTE and Millimeter Waves for V2I Communications: an End-to-End Performance Comparison
Venue: arXiv cs.NI 2019
Year: 2019

The Long Term Evolution (LTE) standard enables, besides cellular connectivity, basic automotive services to promote road safety through vehicle-to-infrastructure (V2I) communications. Nevertheless, stakeholders and research institutions, driven by the ambitious technological advances expected from fully autonomous and intelligent transportation systems, have recently investigated new radio technologies as a means to support vehicular applications. In particular, the millimeter wave (mmWave) spectrum holds great promise because of the large available bandwidth that may provide the required link capacity. Communications at high frequencies, however, suffer from severe propagation and absorption loss, which may cause communication disconnections especially considering high mobility scenarios. It is therefore important to validate, through simulations, the actual feasibility of establishing V2I communications in the above-6 GHz bands. Following this rationale, in this paper we provide the first comparative end-to-end evaluation of the performance of the LTE and mmWave technologies in a vehicular scenario. The simulation framework includes detailed measurement-based channel models as well as the full details of MAC, RLC and transport protocols. Our results show that, although LTE still represents a promising access solution to guarantee robust and fair connections, mmWaves satisfy the foreseen extreme throughput demands of most emerging automotive applications.
Scaling up deep neural networks: a capacity allocation perspective
Venue: arXiv cs.LG 2019
Year: 2019

Following the recent work on capacity allocation, we formulate the conjecture that the shattering problem in deep neural networks can only be avoided if the capacity propagation through layers has a non-degenerate continuous limit when the number of layers tends to infinity. This allows us to study a number of commonly used architectures and determine which scaling relations should be enforced in practice as the number of layers grows large. In particular, we recover the conditions of Xavier initialization in the multi-channel case, and we find that weights and biases should be scaled down as the inverse square root of the number of layers for deep residual networks and as the inverse square root of the desired memory length for recurrent networks.
Multi-Agent Deep Reinforcement Learning for Large-scale Traffic Signal Control
Venue: arXiv cs.LG 2019
Year: 2019

Reinforcement learning (RL) is a promising data-driven approach for adaptive traffic signal control (ATSC) in complex urban traffic networks, and deep neural networks further enhance its learning power. However, centralized RL is infeasible for large-scale ATSC due to the extremely high dimension of the joint action space. Multi-agent RL (MARL) overcomes the scalability issue by distributing the global control to each local RL agent, but it introduces new challenges: now the environment becomes partially observable from the viewpoint of each local agent due to limited communication among agents. Most existing studies in MARL focus on designing efficient communication and coordination among traditional Q-learning agents. This paper presents, for the first time, a fully scalable and decentralized MARL algorithm for the state-of-the-art deep RL agent: advantage actor critic (A2C), within the context of ATSC. In particular, two methods are proposed to stabilize the learning procedure, by improving the observability and reducing the learning difficulty of each local agent. The proposed multi-agent A2C is compared against independent A2C and independent Q-learning algorithms, in both a large synthetic traffic grid and a large real-world traffic network of Monaco city, under simulated peak-hour traffic dynamics. Results demonstrate its optimality, robustness, and sample efficiency over other state-of-the-art decentralized MARL algorithms.
A Quantum Router for the Entangled Web
Venue: arXiv cs.NI 2019
Year: 2019

Qubit transmission protocols are presently point-to-point, and thus restrictive in their functionality. A quantum router is necessary for the quantum Internet to become a reality. We present a quantum router design based on teleportation, as well as mechanisms for entangled pair management. The prototype was validated using a quantum simulator.
Generating superpixels using deep image representations
Venue: arXiv cs.CV 2019
Year: 2019

Superpixel algorithms are a common pre-processing step for computer vision algorithms such as segmentation, object tracking and localization. Many superpixel methods only rely on colors features for segmentation, limiting performance in low-contrast regions and applicability to infrared or medical images where object boundaries have wide appearance variability. We study the inclusion of deep image features in the SLIC superpixel algorithm to exploit higher-level image representations. In addition, we devise a trainable superpixel algorithm, yielding an intermediate domain-specific image representation that can be applied to different tasks. A clustering-based superpixel algorithm is transformed into a pixel-wise classification task and superpixel training data is derived from semantic segmentation datasets. Our results demonstrate that this approach is able to improve superpixel quality consistently.
Graph Colouring Meets Deep Learning: Effective Graph Neural Network Models for Combinatorial Problems
Venue: arXiv cs.LG 2019
Year: 2019

Deep learning has consistently defied state-of-the-art techniques in many fields over the last decade. However, we are just beginning to understand the capabilities of neural learning in symbolic domains. Deep learning architectures that employ parameter sharing over graphs can produce models which can be trained on complex properties of relational data. These include highly relevant NP-Complete problems, such as SAT and TSP. In this work, we showcase how Graph Neural Networks (GNN) can be engineered -- with a very simple architecture -- to solve the fundamental combinatorial problem of graph colouring. Our results show that the model, which achieves high accuracy upon training on random instances, is able to generalise to graph distributions different from those seen at training time. Further, it performs better than the Neurosat, Tabucol and greedy baselines for some distributions. In addition, we show how vertex embeddings can be clustered in multidimensional spaces to yield constructive solutions even though our model is only trained as a binary classifier. In summary, our results contribute to shorten the gap in our understanding of the algorithms learned by GNNs, as well as hoarding empirical evidence for their capability on hard combinatorial problems. Our results thus contribute to the standing challenge of integrating robust learning and symbolic reasoning in Deep Learning systems.
Fast Registration for cross-source point clouds by using weak regional affinity and pixel-wise refinement
Venue: arXiv cs.CV 2019
Year: 2019

Many types of 3D acquisition sensors have emerged in recent years and point cloud has been widely used in many areas. Accurate and fast registration of cross-source 3D point clouds from different sensors is an emerged research problem in computer vision. This problem is extremely challenging because cross-source point clouds contain a mixture of various variances, such as density, partial overlap, large noise and outliers, viewpoint changing. In this paper, an algorithm is proposed to align cross-source point clouds with both high accuracy and high efficiency. There are two main contributions: firstly, two components, the weak region affinity and pixel-wise refinement, are proposed to maintain the global and local information of 3D point clouds. Then, these two components are integrated into an iterative tensor-based registration algorithm to solve the cross-source point cloud registration problem. We conduct experiments on synthetic cross-source benchmark dataset and real cross-source datasets. Comparison with six state-of-the-art methods, the proposed method obtains both higher efficiency and accuracy.