OpenRaiser/Intern-Atlas huggingface dataset:
Self-guided Approximate Linear Programs
Venue: arXiv cs.LG 2021
Year: 2021

Approximate linear programs (ALPs) are well-known models based on value function approximations (VFAs) to obtain policies and lower bounds on the optimal policy cost of discounted-cost Markov decision processes (MDPs). Formulating an ALP requires (i) basis functions, the linear combination of which defines the VFA, and (ii) a state-relevance distribution, which determines the relative importance of different states in the ALP objective for the purpose of minimizing VFA error. Both these choices are typically heuristic: basis function selection relies on domain knowledge while the state-relevance distribution is specified using the frequency of states visited by a heuristic policy. We propose a self-guided sequence of ALPs that embeds random basis functions obtained via inexpensive sampling and uses the known VFA from the previous iteration to guide VFA computation in the current iteration. Self-guided ALPs mitigate the need for domain knowledge during basis function selection as well as the impact of the initial choice of the state-relevance distribution, thus significantly reducing the ALP implementation burden. We establish high probability error bounds on the VFAs from this sequence and show that a worst-case measure of policy performance is improved. We find that these favorable implementation and theoretical properties translate to encouraging numerical results on perishable inventory control and options pricing applications, where self-guided ALP policies improve upon policies from problem-specific methods. More broadly, our research takes a meaningful step toward application-agnostic policies and bounds for MDPs.
Co-evolution of language and agents in referential games
Venue: arXiv cs.CL 2021
Year: 2021

Referential games offer a grounded learning environment for neural agents which accounts for the fact that language is functionally used to communicate. However, they do not take into account a second constraint considered to be fundamental for the shape of human language: that it must be learnable by new language learners. Cogswell et al. (2019) introduced cultural transmission within referential games through a changing population of agents to constrain the emerging language to be learnable. However, the resulting languages remain inherently biased by the agents' underlying capabilities. In this work, we introduce Language Transmission Engine to model both cultural and architectural evolution in a population of agents. As our core contribution, we empirically show that the optimal situation is to take into account also the learning biases of the language learners and thus let language and agents co-evolve. When we allow the agent population to evolve through architectural evolution, we achieve across the board improvements on all considered metrics and surpass the gains made with cultural transmission. These results stress the importance of studying the underlying agent architecture and pave the way to investigate the co-evolution of language and agent in language emergence studies.
Are you still with me? Continuous Engagement Assessment from a Robot's Point of View
Venue: arXiv cs.RO 2021
Year: 2021

Continuously measuring the engagement of users with a robot in a Human-Robot Interaction (HRI) setting paves the way towards in-situ reinforcement learning, improve metrics of interaction quality, and can guide interaction design and behaviour optimisation. However, engagement is often considered very multi-faceted and difficult to capture in a workable and generic computational model that can serve as an overall measure of engagement. Building upon the intuitive ways humans successfully can assess situation for a degree of engagement when they see it, we propose a novel regression model (utilising CNN and LSTM networks) enabling robots to compute a single scalar engagement during interactions with humans from standard video streams, obtained from the point of view of an interacting robot. The model is based on a long-term dataset from an autonomous tour guide robot deployed in a public museum, with continuous annotation of a numeric engagement assessment by three independent coders. We show that this model not only can predict engagement very well in our own application domain but show its successful transfer to an entirely different dataset (with different tasks, environment, camera, robot and people). The trained model and the software is available to the HRI community as a tool to measure engagement in a variety of settings.
Partially symmetric monomial codes
Venue: arXiv cs.IT 2021
Year: 2021

A framework of monomial codes is considered, which includes linear codes generated by the evaluation of certain monomials. Polar and Reed-Muller codes are the two best-known representatives of such codes and can be considered as two extreme cases. Reed-Muller codes have a large automorphism group but their low-complexity maximum likelihood decoding still remains an open problem. On the other hand, polar codes have much less symmetries but admit the efficient near-ML decoding. We study the dependency between the code symmetries and the decoding efficiency. We introduce a new family of codes, partially symmetric monomial codes. These codes have a smaller group of symmetries than the Reed-Muller codes and are in this sense "between" RM and polar codes. A lower bound on their parameters is introduced along with the explicit construction which achieves it. Structural properties of these codes are demonstrated and it is shown that they often have a recursive structure.
Aggregated Learning: A Vector-Quantization Approach to Learning Neural Network Classifiers
Venue: arXiv cs.LG 2021
Year: 2021

We consider the problem of learning a neural network classifier. Under the information bottleneck (IB) principle, we associate with this classification problem a representation learning problem, which we call "IB learning". We show that IB learning is, in fact, equivalent to a special class of the quantization problem. The classical results in rate-distortion theory then suggest that IB learning can benefit from a "vector quantization" approach, namely, simultaneously learning the representations of multiple input objects. Such an approach assisted with some variational techniques, result in a novel learning framework, "Aggregated Learning", for classification with neural network models. In this framework, several objects are jointly classified by a single neural network. The effectiveness of this framework is verified through extensive experiments on standard image recognition and text classification tasks.
Exploiting Database Management Systems and Treewidth for Counting
Venue: arXiv cs.AI 2021
Year: 2021

Bounded treewidth is one of the most cited combinatorial invariants, which was applied in the literature for solving several counting problems efficiently. A canonical counting problem is #SAT, which asks to count the satisfying assignments of a Boolean formula. Recent work shows that benchmarking instances for #SAT often have reasonably small treewidth. This paper deals with counting problems for instances of small treewidth. We introduce a general framework to solve counting questions based on state-of-the-art database management systems (DBMS). Our framework takes explicitly advantage of small treewidth by solving instances using dynamic programming (DP) on tree decompositions (TD). Therefore, we implement the concept of DP into a DBMS (PostgreSQL), since DP algorithms are already often given in terms of table manipulations in theory. This allows for elegant specifications of DP algorithms and the use of SQL to manipulate records and tables, which gives us a natural approach to bring DP algorithms into practice. To the best of our knowledge, we present the first approach to employ a DBMS for algorithms on TDs. A key advantage of our approach is that DBMS naturally allow to deal with huge tables with a limited amount of main memory (RAM), parallelization, as well as suspending computation.
A reconciliation approach to key generation based on Module-LWE
Venue: arXiv cs.CR 2021
Year: 2021

We consider a key encapsulation mechanism (KEM) based on Module-LWE where reconciliation is performed on the 8-dimensional lattice $E_8$, which admits a fast CVP algorithm. Our scheme generates 256 bits of key and requires 3 or 4 bits of reconciliation per dimension. We show that it can outperform Kyber in terms of the modulus q with comparable error probability. We prove that our protocol is IND-CPA secure and improves the security level of Kyber by 7.3%.
Universal Differential Equations for Scientific Machine Learning
Venue: arXiv cs.LG 2021
Year: 2021

In the context of science, the well-known adage "a picture is worth a thousand words" might well be "a model is worth a thousand datasets." In this manuscript we introduce the SciML software ecosystem as a tool for mixing the information of physical laws and scientific models with data-driven machine learning approaches. We describe a mathematical object, which we denote universal differential equations (UDEs), as the unifying framework connecting the ecosystem. We show how a wide variety of applications, from automatically discovering biological mechanisms to solving high-dimensional Hamilton-Jacobi-Bellman equations, can be phrased and efficiently handled through the UDE formalism and its tooling. We demonstrate the generality of the software tooling to handle stochasticity, delays, and implicit constraints. This funnels the wide variety of SciML applications into a core set of training mechanisms which are highly optimized, stabilized for stiff equations, and compatible with distributed parallelism and GPU accelerators.
What's Live? Understanding Distributed Consensus
Venue: arXiv cs.DC 2021
Year: 2021

Distributed consensus algorithms such as Paxos have been studied extensively. They all use the same definition of safety. Liveness is especially important in practice despite well-known theoretical impossibility results. However, many different liveness properties and assumptions have been stated, and there are no systematic comparisons for better understanding of these properties. This paper systematically studies and compares different liveness properties stated for over 30 prominent consensus algorithms and variants. We introduce a precise high-level language and formally specify these properties in the language. We then create a hierarchy of liveness properties combining two hierarchies of the assumptions used and a hierarchy of the assertions made, and compare the strengths and weaknesses of algorithms that ensure these properties. Our formal specifications and systematic comparisons led to the discovery of a range of problems in various stated liveness properties, from too weak assumptions for which no liveness assertions can hold, to too strong assumptions making it trivial to achieve the assertions. We also developed TLA+ specifications of these liveness properties, and we use model checking of execution steps to illustrate liveness patterns for Paxos.
Variational system identification of the partial differential equations governing microstructure evolution in materials: Inference over sparse and spatially unrelated data
Venue: arXiv cs.CE 2021
Year: 2021

Pattern formation is a widely observed phenomenon in diverse fields including materials physics, developmental biology and ecology, among many others. The physics underlying the patterns is specific to the mechanisms, and is encoded by partial differential equations (PDEs). With the aim of discovering hidden physics, we have previously presented a variational approach to identifying such systems of PDEs in the face of noisy data at varying fidelities (Computer Methods in Applied Mechanics and Engineering, 353:201-216, 2019). Here, we extend our variational system identification methods to address the challenges presented by image data on microstructures in materials physics. PDEs are formally posed as initial and boundary value problems over combinations of time intervals and spatial domains whose evolution is either fixed or can be tracked. However, the vast majority of microscopy techniques for evolving microstructure in a given material system deliver micrographs of pattern evolution over domains that bear no relation with each other at different time instants. The temporal resolution can rarely capture the fastest time scales that dominate the early dynamics, and noise abounds. Furthermore, data for evolution of the same phenomenon in a material system may well be obtained from different physical specimens. Against this backdrop of spatially unrelated, sparse and multi-source data, we exploit the variational framework to make judicious choices of weighting functions and identify PDE operators from the dynamics. A consistency condition arises for parsimonious inference of a minimal set of the spatial operators at steady state. It is complemented by a confirmation test that provides a sharp condition for acceptance of the inferred operators. The entire framework is demonstrated on synthetic data that reflect the characteristics of the experimental material microscopy images.
A Content-Based Deep Intrusion Detection System
Venue: arXiv cs.NI 2021
Year: 2021

The growing number of Internet users and the prevalence of web applications make it necessary to deal with very complex software and applications in the network. This results in an increasing number of new vulnerabilities in the systems, and leading to an increase in cyber threats and, in particular, zero-day attacks. The cost of generating appropriate signatures for these attacks is a potential motive for using machine learning-based methodologies. Although there are many studies on using learning-based methods for attack detection, they generally use extracted features and overlook raw contents. This approach can lessen the performance of detection systems against content-based attacks like SQL injection, Cross-site Scripting (XSS), and various viruses. In this work, we propose a framework, called deep intrusion detection (DID) system, that uses the pure content of traffic flows in addition to traffic metadata in the learning and detection phases of a passive DNN IDS. To this end, we deploy and evaluate an offline IDS following the framework using LSTM as a deep learning technique. Due to the inherent nature of deep learning, it can process high dimensional data content and, accordingly, discover the sophisticated relations between the auto extracted features of the traffic. To evaluate the proposed DID system, we use the CIC-IDS2017 and CSE-CIC-IDS2018 datasets. The evaluation metrics, such as precision and recall, reach $0.992$ and $0.998$ on CIC-IDS2017, and $0.933$ and $0.923$ on CSE-CIC-IDS2018 respectively, which show the high performance of the proposed DID method.
Strong Progress for Session-Typed Processes in a Linear Metalogic with Circular Proofs
Venue: arXiv cs.LO 2021
Year: 2021

We introduce an infinitary first order linear logic with least and greatest fixed points. To ensure cut elimination, we impose a validity condition on infinite derivations. Our calculus is designed to reason about rich signatures of mutually defined inductive and coinductive linear predicates. In a major case study we use it to prove the strong progress property for binary session-typed processes under an asynchronous communication semantics. As far as we are aware, this is the first proof of this property.
Throughput Optimal Routing in Blockchain Based Payment Systems
Venue: arXiv cs.DC 2021
Year: 2021

Cryptocurrency networks such as Bitcoin have emerged as a distributed alternative to traditional centralized financial transaction networks. However, there are major challenges in scaling up the throughput of such networks. Lightning network and Spider network are alternates that build bidirectional payment channels on top of cryptocurrency networks using smart contracts, to enable fast transactions that bypass the Blockchain. In this paper, we study the problem of routing transactions in such a payment processing network. We first propose a Stochastic model to study such a system, as opposed to a fluid model that is studied in the literature. Each link in such a model is a two-sided queue, and unlike classical queues, such queues are not stable unless there is an external control. We propose a notion of stability for the payment processing network consisting of such two-sided queues using the notion of on-chain rebalancing. We then characterize the capacity region and propose a throughput optimal algorithm that stabilizes the system under any load within the capacity region. The stochastic model enables us to study closed loop policies, which typically have better queuing/delay performance than the open loop policies (or static split rules) studied in the literature. We investigate this through simulations.
Computationally easy, spectrally good multipliers for congruential pseudorandom number generators
Venue: arXiv cs.DS 2021
Year: 2021

Congruential pseudorandom number generators rely on good multipliers, that is, integers that have good performance with respect to the spectral test. We provide lists of multipliers with a good lattice structure up to dimension eight and up to lag eight for generators with typical power-of-two moduli, analyzing in detail multipliers close to the square root of the modulus, whose product can be computed quickly.
Smart Data driven Decision Trees Ensemble Methodology for Imbalanced Big Data
Venue: arXiv cs.LG 2021
Year: 2021

Differences in data size per class, also known as imbalanced data distribution, have become a common problem affecting data quality. Big Data scenarios pose a new challenge to traditional imbalanced classification algorithms, since they are not prepared to work with such amount of data. Split data strategies and lack of data in the minority class due to the use of MapReduce paradigm have posed new challenges for tackling the imbalance between classes in Big Data scenarios. Ensembles have shown to be able to successfully address imbalanced data problems. Smart Data refers to data of enough quality to achieve high performance models. The combination of ensembles and Smart Data, achieved through Big Data preprocessing, should be a great synergy. In this paper, we propose a novel Smart Data driven Decision Trees Ensemble methodology for addressing the imbalanced classification problem in Big Data domains, namely SD_DeTE methodology. This methodology is based on the learning of different decision trees using distributed quality data for the ensemble process. This quality data is achieved by fusing Random Discretization, Principal Components Analysis and clustering-based Random Oversampling for obtaining different Smart Data versions of the original data. Experiments carried out in 21 binary adapted datasets have shown that our methodology outperforms Random Forest.
Modular coinduction up-to for higher-order languages via first-order transition systems
Venue: arXiv cs.LO 2021
Year: 2021

The bisimulation proof method can be enhanced by employing `bisimulations up-to' techniques. A comprehensive theory of such enhancements has been developed for first-order (i.e., CCS-like) labelled transition systems (LTSs) and bisimilarity, based on abstract fixed-point theory and compatible functions. We transport this theory onto languages whose bisimilarity and LTS go beyond those of first-order models. The approach consists in exhibiting fully abstract translations of the more sophisticated LTSs and bisimilarities onto the first-order ones. This allows us to reuse directly the large corpus of up-to techniques that are available on first-order LTSs. The only ingredient that has to be manually supplied is the compatibility of basic up-to techniques that are specific to the new languages. We investigate the method on the pi-calculus, the lambda-calculus, and a (call-by-value) lambda-calculus with references.
Transparently Capturing Request Execution Path for Anomaly Detection
Venue: arXiv cs.DC 2021
Year: 2021

With the increasing scale and complexity of cloud systems and big data analytics platforms, it is becoming more and more challenging to understand and diagnose the processing of a service request in such distributed platforms. One way that helps to deal with this problem is to capture the complete end-to-end execution path of service requests among all involved components accurately. This paper presents REPTrace, a generic methodology for capturing such execution paths in a transparent fashion. We analyze a comprehensive list of execution scenarios, and propose principles and algorithms for generating the end-to-end request execution path for all the scenarios. Moreover, this paper presents an anomaly detection approach exploiting request execution paths to detect anomalies of the execution during request processing. The experiments on four popular distributed platforms with different workloads show that REPTrace can transparently capture the accurate request execution path with reasonable latency and negligible network overhead. Fault injection experiments show that execution anomalies are detected with high recall (96%).
Vector Single-Source Surface Integral Equation for TE Scattering From Cylindrical Multilayered Objects
Venue: arXiv cs.CE 2021
Year: 2021

A single-source surface integral equation (SS-SIE) for transverse electric (TE) scattering from cylindrical multilayered objects is proposed in this paper. By incorporating the differential surface admittance operator (DSAO) and recursively applying the surface equivalence theorem from innermost to outermost boundaries, an equivalent model with only electric current density on the outermost boundary can be obtained. In addition, an integration approach is proposed, where the small argument expansion of the Hankel function is used to evaluate the singular and nearly singular integrals. Compared with other SIEs, such as the Poggio-Miller-Chang-Harrington-Wu-Tsai (PMCHWT) formulation, the computational expenditure is reduced for multilayered structures because only a single source is needed on the outermost boundary. As shown in the numerical results, the proposed method generates only 19% of unknowns, uses 26% of memory, and requires 29% of the CPU time of the PMCHWT formulation.
Explaining Data-Driven Decisions made by AI Systems: The Counterfactual Approach
Venue: arXiv cs.LG 2021
Year: 2021

We examine counterfactual explanations for explaining the decisions made by model-based AI systems. The counterfactual approach we consider defines an explanation as a set of the system's data inputs that causally drives the decision (i.e., changing the inputs in the set changes the decision) and is irreducible (i.e., changing any subset of the inputs does not change the decision). We (1) demonstrate how this framework may be used to provide explanations for decisions made by general, data-driven AI systems that may incorporate features with arbitrary data types and multiple predictive models, and (2) propose a heuristic procedure to find the most useful explanations depending on the context. We then contrast counterfactual explanations with methods that explain model predictions by weighting features according to their importance (e.g., SHAP, LIME) and present two fundamental reasons why we should carefully consider whether importance-weight explanations are well-suited to explain system decisions. Specifically, we show that (i) features that have a large importance weight for a model prediction may not affect the corresponding decision, and (ii) importance weights are insufficient to communicate whether and how features influence decisions. We demonstrate this with several concise examples and three detailed case studies that compare the counterfactual approach with SHAP to illustrate various conditions under which counterfactual explanations explain data-driven decisions better than importance weights.