OpenRaiser/Intern-Atlas huggingface dataset:
Offloading and Resource Allocation with General Task Graph in Mobile Edge Computing: A Deep Reinforcement Learning Approach
Venue: arXiv cs.NI 2020
Year: 2020

In this paper, we consider a mobile-edge computing system, where an access point assists a mobile device (MD) to execute an application consisting of multiple tasks following a general task call graph. The objective is to jointly determine the offloading decision of each task and the resource allocation under time-varying wireless fading channels and stochastic edge computing capability, so that the energy-time cost (ETC) of the MD is minimized. Solving the problem is particularly hard due to the combinatorial offloading decisions and the strong coupling among task executions under the general dependency model. Conventional numerical optimization methods are inefficient to solve such a problem, especially when the problem size is large. To address the issue, we propose a deep reinforcement learning (DRL) framework based on the actor-critic learning structure. In particular, the actor network utilizes a DNN to learn the optimal mapping from the input states to the binary offloading decision of each task. Meanwhile, by analyzing the structure of the optimal solution, we derive a low-complexity algorithm for the critic network to quickly evaluate the ETC performance of the offloading decisions output by the actor network. With the low-complexity critic network, we can quickly select the best offloading action and subsequently store the state-action pair in an experience replay memory as the training dataset to continuously improve the action generation DNN. To further reduce the complexity, we show that the optimal offloading decision exhibits an one-climb structure, which can be utilized to significantly reduce the search space of action generation. Numerical results show that for various types of task graphs, the proposed algorithm achieves up to $99.1\%$ of the optimal performance while significantly reducing the computational complexity compared to the existing optimization methods.
Honing and proofing Astrophysical codes on the road to Exascale. Experiences from code modernization on many-core systems
Venue: arXiv cs.DC 2020
Year: 2020

The complexity of modern and upcoming computing architectures poses severe challenges for code developers and application specialists, and forces them to expose the highest possible degree of parallelism, in order to make the best use of the available hardware. The Intel$^{(R)}$ Xeon Phi$^{(TM)}$ of second generation (code-named Knights Landing, henceforth KNL) is the latest many-core system, which implements several interesting hardware features like for example a large number of cores per node (up to 72), the 512 bits-wide vector registers and the high-bandwidth memory. The unique features of KNL make this platform a powerful testbed for modern HPC applications. The performance of codes on KNL is therefore a useful proxy of their readiness for future architectures. In this work we describe the lessons learnt during the optimisation of the widely used codes for computational astrophysics P-Gadget-3, Flash and Echo. Moreover, we present results for the visualisation and analysis tools VisIt and yt. These examples show that modern architectures benefit from code optimisation at different levels, even more than traditional multi-core systems. However, the level of modernisation of typical community codes still needs improvements, for them to fully utilise resources of novel architectures.
Imprecise Probability for Multiparty Session Types in Process Algebra
Venue: arXiv cs.LO 2020
Year: 2020

In this paper we introduce imprecise probability for session types. More exactly, we use a probabilistic process calculus in which both nondeterministic external choice and probabilistic internal choice are considered. We propose the probabilistic multiparty session types able to codify the structure of the communications by using some imprecise probabilities given in terms of lower and upper probabilities. We prove that this new probabilistic typing system is sound, as well as several other results dealing with both classical and probabilistic properties. The approach is illustrated by a simple example inspired by survey polls.
On Computability of Data Word Functions Defined by Transducers
Venue: arXiv cs.LO 2020
Year: 2020

In this paper, we investigate the problem of synthesizing computable functions of infinite words over an infinite alphabet (data omega-words). The notion of computability is defined through Turing machines with infinite inputs which can produce the corresponding infinite outputs in the limit. We use non-deterministic transducers equipped with registers, an extension of register automata with outputs, to specify functions. Such transducers may not define functions but more generally relations of data omega-words, and we show that it is PSpace-complete to test whether a given transducer defines a function. Then, given a function defined by some register transducer, we show that it is decidable (and again, PSpace-complete) whether such function is computable. As for the known finite alphabet case, we show that computability and continuity coincide for functions defined by register transducers, and show how to decide continuity. We also define a subclass for which those problems are solvable in polynomial time.
Subexponential parameterized algorithms and kernelization on almost chordal graphs
Venue: arXiv cs.DS 2020
Year: 2020

We study the algorithmic properties of the graph class Chordal-ke, that is, graphs that can be turned into a chordal graph by adding at most k edges or, equivalently, the class of graphs of fill-in at most k. We discover that a number of fundamental intractable optimization problems being parameterized by k admit subexponential algorithms on graphs from Chordal-ke. We identify a large class of optimization problems on Chordal-ke that admit algorithms with the typical running time 2^{O(\sqrt{k}\log k)}\cdot n^{O(1)}. Examples of the problems from this class are finding an independent set of maximum weight, finding a feedback vertex set or an odd cycle transversal of minimum weight, or the problem of finding a maximum induced planar subgraph. On the other hand, we show that for some fundamental optimization problems, like finding an optimal graph coloring or finding a maximum clique, are FPT on Chordal-ke when parameterized by k but do not admit subexponential in k algorithms unless ETH fails. Besides subexponential time algorithms, the class of Chordal-ke graphs appears to be appealing from the perspective of kernelization (with parameter k). While it is possible to show that most of the weighted variants of optimization problems do not admit polynomial in k kernels on Chordal-ke graphs, this does not exclude the existence of Turing kernelization and kernelization for unweighted graphs. In particular, we construct a polynomial Turing kernel for Weighted Clique on Chordal-ke graphs. For (unweighted) Independent Set we design polynomial kernels on two interesting subclasses of Chordal-ke, namely, Interval-ke and Split-ke graphs.
A note on the explicit constructions of tree codes over polylogarithmic-sized alphabet
Venue: arXiv cs.CC 2020
Year: 2020

Recently, Cohen, Haeupler and Schulman gave an explicit construction of binary tree codes over polylogarithmic-sized output alphabet based on Pudlák's construction of maximum-distance-separable (MDS) tree codes using totally-non-singular triangular matrices. In this short note, we give a unified and simpler presentation of Pudlák and Cohen-Haeupler-Schulman's constructions.
AI Online Filters to Real World Image Recognition
Venue: arXiv cs.CV 2020
Year: 2020

Deep artificial neural networks, trained with labeled data sets are widely used in numerous vision and robotics applications today. In terms of AI, these are called reflex models, referring to the fact that they do not self-evolve or actively adapt to environmental changes. As demand for intelligent robot control expands to many high level tasks, reinforcement learning and state based models play an increasingly important role. Herein, in computer vision and robotics domain, we study a novel approach to add reinforcement controls onto the image recognition reflex models to attain better overall performance, specifically to a wider environment range beyond what is expected of the task reflex models. Follow a common infrastructure with environment sensing and AI based modeling of self-adaptive agents, we implement multiple types of AI control agents. To the end, we provide comparative results of these agents with baseline, and an insightful analysis of their benefit to improve overall image recognition performance in real world.
Multilogue-Net: A Context Aware RNN for Multi-modal Emotion Detection and Sentiment Analysis in Conversation
Venue: arXiv cs.CL 2020
Year: 2020

Sentiment Analysis and Emotion Detection in conversation is key in several real-world applications, with an increase in modalities available aiding a better understanding of the underlying emotions. Multi-modal Emotion Detection and Sentiment Analysis can be particularly useful, as applications will be able to use specific subsets of available modalities, as per the available data. Current systems dealing with Multi-modal functionality fail to leverage and capture - the context of the conversation through all modalities, the dependency between the listener(s) and speaker emotional states, and the relevance and relationship between the available modalities. In this paper, we propose an end to end RNN architecture that attempts to take into account all the mentioned drawbacks. Our proposed model, at the time of writing, out-performs the state of the art on a benchmark dataset on a variety of accuracy and regression metrics.
Variational Encoder-based Reliable Classification
Venue: arXiv cs.LG 2020
Year: 2020

Machine learning models provide statistically impressive results which might be individually unreliable. To provide reliability, we propose an Epistemic Classifier (EC) that can provide justification of its belief using support from the training dataset as well as quality of reconstruction. Our approach is based on modified variational auto-encoders that can identify a semantically meaningful low-dimensional space where perceptually similar instances are close in $\ell_2$-distance too. Our results demonstrate improved reliability of predictions and robust identification of samples with adversarial attacks as compared to baseline of softmax-based thresholding.
Proceedings of the VIII International Workshop on Locational Analysis and Related Problems
Venue: arXiv cs.OH 2020
Year: 2020

The International Workshop on Locational Analysis and Related Problems will take place during September 27-29, 2017 in Segovia (Spain). It is organized by the Spanish Location Network and Location Group GELOCA (SEIO). GELOCA is a working group on location belonging to the Statistics and Operations Research Spanish Society. The Spanish Location Network is a group of more than 100 researchers distributed into 16 nodes corresponding to several Spanish universities. The Network has been funded by the Spanish Government. Every year, the Network organizes a meeting to promote the communication between its members and between them and other researchers, and to contribute to the development of the location field and related problems. Previous meetings took place in Málaga (September 14-16, 2016), Barcelona (November 25-28, 2015), Sevilla (October 1-3, 2014), Torremolinos (Málaga, June 19-21, 2013), Granada (May 10-12, 2012), Las Palmas de Gran Canaria (February 2-5, 2011) and Sevilla (February 1-3, 2010). The topics of interest are location analysis and related problems. It includes location, networks, transportation, routing, logistics models, as well as, exact and heuristic solution methods, and computational geometry, among others.
Proceedings of the IX International Workshop on Locational Analysis and Related Problems
Venue: arXiv cs.OH 2020
Year: 2020

The International Workshop on Locational Analysis and Related Problems will take place during January 30-February 1, 2019 in Cádiz (Spain). It is organized by the Spanish Location Network and Location Group GELOCA (SEIO). GELOCA is a working group on location belonging to the Statistics and Operations Research Spanish Society. The Spanish Location Network is a group of more than 140 researchers distributed into 16 nodes corresponding to several Spanish universities. The Network has been funded by the Spanish Government. Every year, the Network organizes a meeting to promote the communication between its members and between them and other researchers, and to contribute to the development of the location field and related problems. Previous meetings took place in Segovia (September 27-29, 2017), Málaga (September 14-16, 2016), Barcelona (November 25-28, 2015), Sevilla (October 1-3, 2014), Torremolinos (Málaga, June 19-21, 2013), Granada (May 10-12, 2012), Las Palmas de Gran Canaria (February 2-5, 2011) and Sevilla (February 1-3, 2010). The topics of interest are location analysis and related problems. It includes location models, networks, transportation, logistics, exact and heuristic solution methods, and computational geometry, among others.
Re-evaluating scaling methods for distributed parallel systems
Venue: arXiv cs.PF 2020
Year: 2020

The paper explains why Amdahl's Law shall be interpreted specifically for distributed parallel systems and why it generated so many debates, discussions, and abuses. We set up a general model and list many of the terms affecting parallel processing. We scrutinize the validity of neglecting certain terms in different approximations, with special emphasis on the famous scaling laws of parallel processing. We clarify that when using the right interpretation of terms, Amdahl's Law is the governing law of all kinds of parallel processing. Amdahl's Law describes among others the history of supercomputing, the inherent performance limitation of the different kinds of parallel processing and it is the basic Law of the 'modern computing' paradigm, that the computing systems working under extreme computing conditions are desperately needed.
Holistic Specifications for Robust Programs
Venue: arXiv cs.PL 2020
Year: 2020

Functional specifications describe what program components do: the sufficient conditions to invoke a component's operations. They allow us to reason about the use of components in the closed world setting, where the component interacts with known client code, and where the client code must establish the appropriate pre-conditions before calling into the component. Sufficient conditions are not enough to reason about the use of components in the open world setting, where the component interacts with external code, possibly of unknown provenance, and where the component itself may evolve over time. In this open world setting, we must also consider the necessary} conditions, i.e, what are the conditions without which an effect will not happen. In this paper we propose the language Chainmail for writing holistic specifications that focus on necessary conditions (as well as sufficient conditions). We give a formal semantics for \Chainmail. The core of Chainmail has been mechanised in the Coq proof assistant.
Multiple Imputation with Denoising Autoencoder using Metamorphic Truth and Imputation Feedback
Venue: arXiv cs.LG 2020
Year: 2020

Although data may be abundant, complete data is less so, due to missing columns or rows. This missingness undermines the performance of downstream data products that either omit incomplete cases or create derived completed data for subsequent processing. Appropriately managing missing data is required in order to fully exploit and correctly use data. We propose a Multiple Imputation model using Denoising Autoencoders to learn the internal representation of data. Furthermore, we use the novel mechanisms of Metamorphic Truth and Imputation Feedback to maintain statistical integrity of attributes and eliminate bias in the learning process. Our approach explores the effects of imputation on various missingness mechanisms and patterns of missing data, outperforming other methods in many standard test cases.
MonoLayout: Amodal scene layout from a single image
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we address the novel, highly challenging problem of estimating the layout of a complex urban driving scenario. Given a single color image captured from a driving platform, we aim to predict the bird's-eye view layout of the road and other traffic participants. The estimated layout should reason beyond what is visible in the image, and compensate for the loss of 3D information due to projection. We dub this problem amodal scene layout estimation, which involves "hallucinating" scene layout for even parts of the world that are occluded in the image. To this end, we present MonoLayout, a deep neural network for real-time amodal scene layout estimation from a single image. We represent scene layout as a multi-channel semantic occupancy grid, and leverage adversarial feature learning to hallucinate plausible completions for occluded image parts. Due to the lack of fair baseline methods, we extend several state-of-the-art approaches for road-layout estimation and vehicle occupancy estimation in bird's-eye view to the amodal setup for rigorous evaluation. By leveraging temporal sensor fusion to generate training labels, we significantly outperform current art over a number of datasets. On the KITTI and Argoverse datasets, we outperform all baselines by a significant margin. We also make all our annotations, and code publicly available. A video abstract of this paper is available https://www.youtube.com/watch?v=HcroGyo6yRQ .
A Generalizable Knowledge Framework for Semantic Indoor Mapping Based on Markov Logic Networks and Data Driven MCMC
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we propose a generalizable knowledge framework for data abstraction, i.e. finding compact abstract model for input data using predefined abstract terms. Based on these abstract terms, intelligent autonomous systems, such as a robot, should be able to make inference according to specific knowledge base, so that they can better handle the complexity and uncertainty of the real world. We propose to realize this framework by combining Markov logic networks (MLNs) and data driven MCMC sampling, because the former are a powerful tool for modelling uncertain knowledge and the latter provides an efficient way to draw samples from unknown complex distributions. Furthermore, we show in detail how to adapt this framework to a certain task, in particular, semantic robot mapping. Based on MLNs, we formulate task-specific context knowledge as descriptive soft rules. Experiments on real world data and simulated data confirm the usefulness of our framework.
Risk-Averse Equilibrium for Games
Venue: arXiv cs.GT 2020
Year: 2020

The term rational has become synonymous with maximizing expected payoff in the definition of the best response in Nash setting. In this work, we consider stochastic games in which players engage only once, or at most a limited number of times. In such games, it may not be rational for players to maximize their expected payoff as they cannot wait for the Law of Large Numbers to take effect. We instead define a new notion of a risk-averse best response, that results in a risk-averse equilibrium (RAE) in which players choose to play the strategy that maximizes the probability of them being rewarded the most in a single round of the game rather than maximizing the expected received reward, subject to the actions of other players. We prove the risk-averse equilibrium to exist in all finite games and numerically compare its performance to Nash equilibrium in finite-time stochastic games.
CopyCat: Controlled Instruction-Level Attacks on Enclaves
Venue: arXiv cs.CR 2020
Year: 2020

The adversarial model presented by trusted execution environments (TEEs) has prompted researchers to investigate unusual attack vectors. One particularly powerful class of controlled-channel attacks abuses page-table modifications to reliably track enclave memory accesses at a page-level granularity. In contrast to noisy microarchitectural timing leakage, this line of deterministic controlled-channel attacks abuses indispensable architectural interfaces and hence cannot be mitigated by tweaking microarchitectural resources. We propose an innovative controlled-channel attack, named CopyCat, that deterministically counts the number of instructions executed within a single enclave code page. We show that combining the instruction counts harvested by CopyCat with traditional, coarse-grained page-level leakage allows the accurate reconstruction of enclave control flow at a maximal instruction-level granularity. CopyCat can identify intra-page and intra-cache line branch decisions that ultimately may only differ in a single instruction, underscoring that even extremely subtle control flow deviations can be deterministically leaked from secure enclaves. We demonstrate the improved resolution and practicality of CopyCat on Intel SGX in an extensive study of single-trace and deterministic attacks against cryptographic implementations, and give novel algorithmic attacks to perform single-trace key extraction that exploit subtle vulnerabilities in the latest versions of widely-used cryptographic libraries. Our findings highlight the importance of stricter verification of cryptographic implementations, especially in the context of TEEs.
On the Versatility of Open Logical Relations: Continuity, Automatic Differentiation, and a Containment Theorem
Venue: arXiv cs.PL 2020
Year: 2020

Logical relations are one of the most powerful techniques in the theory of programming languages, and have been used extensively for proving properties of a variety of higher-order calculi. However, there are properties that cannot be immediately proved by means of logical relations, for instance program continuity and differentiability in higher-order languages extended with real-valued functions. Informally, the problem stems from the fact that these properties are naturally expressed on terms of non-ground type (or, equivalently, on open terms of base type), and there is no apparent good definition for a base case (i.e. for closed terms of ground types). To overcome this issue, we study a generalization of the concept of a logical relation, called \emph{open logical relation}, and prove that it can be fruitfully applied in several contexts in which the property of interest is about expressions of first-order type. Our setting is a simply-typed $λ$-calculus enriched with real numbers and real-valued first-order functions from a given set, such as the one of continuous or differentiable functions. We first prove a containment theorem stating that for any such a collection of functions including projection functions and closed under function composition, any well-typed term of first-order type denotes a function belonging to that collection. Then, we show by way of open logical relations the correctness of the core of a recently published algorithm for forward automatic differentiation. Finally, we define a refinement-based type system for local continuity in an extension of our calculus with conditionals, and prove the soundness of the type system using open logical relations.