OpenRaiser/Intern-Atlas huggingface dataset:
Lower Bound on Derivatives of Costa's Differential Entropy
Venue: arXiv cs.IT 2020
Year: 2020

Several conjectures concern the lower bound for the differential entropy $H(X_t)$ of an $n$-dimensional random vector $X_t$ introduced by Costa. Cheng and Geng conjectured that $H(X_t)$ is completely monotone, that is, $C_1(m,n): (-1)^{m+1}(d^m/d^m t)H(X_t)\ge0$. McKean conjectured that Gaussian $X_{Gt}$ achieves the minimum of $(-1)^{m+1}(d^m/d^m t)H(X_t)$ under certain conditions, that is, $C_2(m,n): (-1)^{m+1}(d^m/d^m t)H(X_t)\ge(-1)^{m+1}(d^m/d^m t)H(X_{Gt})$. McKean's conjecture was only considered in the univariate case before: $C_2(1,1)$ and $C_2(2,1)$ were proved by McKean and $C_2(i,1),i=3,4,5$ were proved by Zhang-Anantharam-Geng under the log-concave condition. In this paper, we prove $C_2(1,n)$, $C_2(2,n)$ and observe that McKean's conjecture might not be true for $n>1$ and $m>2$. We further propose a weaker version $C_3(m,n): (-1)^{m+1}(d^m/d^m t)H(X_t)\ge(-1)^{m+1}\frac{1}{n}(d^m/d^m t)H(X_{Gt})$ and prove $C_3(3,2)$, $C_3(3,3)$, $C_3(3,4)$, $C_3(4,2)$ under the log-concave condition. A systematical procedure to prove $C_l(m,n)$ is proposed based on semidefinite programming and the results mentioned above are proved using this procedure.
Conceptual Modeling of Time for Computational Ontologies
Venue: arXiv cs.AI 2020
Year: 2020

To provide a foundation for conceptual modeling, ontologies have been introduced to specify the entities, the existences of which are acknowledged in the model. Ontologies are essential components as mechanisms to model a portion of reality in software engineering. In this context, a model refers to a description of objects and processes that populate a system. Developing such a description constrains and directs the design, development, and use of the corresponding system, thus avoiding such difficulties as conflicts and lack of a common understanding. In this cross-area research between modeling and ontology, there has been a growing interest in the development and use of domain ontologies (e.g., Resource Description Framework, Ontology Web Language). This paper contributes to the establishment of a broad ontological foundation for conceptual modeling in a specific domain through proposing a workable ontology (abbreviated as TM). A TM is a one-category ontology called a thimac (things/machines) that is used to elaborate the design and analysis of ontological presumptions. The focus of the study is on such notions as change, event, and time. Several current ontological difficulties are reviewed and remodeled in the TM. TM modeling is also contrasted with time representation in SysML. The results demonstrate that a TM is a useful tool for addressing these ontological problems.
Analysing Meso and Macro conversation structures in an online suicide support forum
Venue: arXiv cs.SI 2020
Year: 2020

Platforms like Reddit and Twitter offer internet users an opportunity to talk about diverse issues, including those pertaining to physical and mental health. Some of these forums also function as a safe space for severely distressed mental health patients to get social support from peers. The online community platform Reddit's SuicideWatch is one example of an online forum dedicated specifically to people who suffer from suicidal thoughts, or who are concerned about people who might be at risk. It remains to be seen if these forums can be used to understand and model the nature of online social support, not least because of the noisy and informal nature of conversations. Moreover, understanding how a community of volunteering peers react to calls for help in cases of suicidal posts, would help to devise better tools for online mitigation of such episodes. In this paper, we propose an approach to characterise conversations in online forums. Using data from the SuicideWatch subreddit as a case study, we propose metrics at a macroscopic level -- measuring the structure of the entire conversation as a whole. We also develop a framework to measure structures in supportive conversations at a mesoscopic level -- measuring interactions with the immediate neighbours of the person in distress. We statistically show through comparison with baseline conversations from random Reddit threads that certain macro and meso-scale structures in an online conversation exhibit signatures of social support, and are particularly over-expressed in SuicideWatch conversations.
Privacy-Preserving Multi-Operator Contact Tracing for Early Detection of Covid19 Contagions
Venue: arXiv cs.CR 2020
Year: 2020

The outbreak of coronavirus disease 2019 (covid-19) is imposing a severe worldwide lock-down. Contact tracing based on smartphones' applications (apps) has emerged as a possible solution to trace contagions and enforce a more sustainable selective quarantine. However, a massive adoption of these apps is required to reach the critical mass needed for effective contact tracing. As an alternative, geo-location technologies in next generation networks (e.g., 5G) can enable Mobile Operators (MOs) to perform passive tracing of users' mobility and contacts with a promised accuracy of down to one meter. To effectively detect contagions, the identities of positive individuals, which are known only by a Governmental Authority (GA), are also required. Note that, besides being extremely sensitive, these data might also be critical from a business perspective. Hence, MOs and the GA need to exchange and process users' geo-locations and infection status data in a privacy-preserving manner. In this work, we propose a privacy-preserving protocol that enables multiple MOs and the GA to share and process users' data to make only the final users discover the number of their contacts with positive individuals. The protocol is based on existing privacy-enhancing strategies that guarantee that users' mobility and infection status are only known to their MOs and to the GA, respectively. From extensive simulations, we observe that the cost to guarantee total privacy (evaluated in terms of data overhead introduced by the protocol) is acceptable, and can also be significantly reduced if we accept a negligible compromise in users' privacy.
Agent-Based Software Testing: A Definition and Systematic Mapping Study
Venue: arXiv cs.SE 2020
Year: 2020

The emergence of new technologies in software testing has increased the automation and flexibility of the testing process. In this context, the adoption of agents in software testing remains an active research area in which various agent methodologies, architectures, and tools are employed to improve different test problems. Even though research that investigates agents in software testing has been growing, these agent-based techniques should be considered in a broader perspective. In order to provide a comprehensive overview of this research area, which we define as agent-based software testing (ABST), a systematic mapping study has been conducted. This mapping study aims to identify the topics studied within ABST, as well as examine the adopted research methodologies, identify the gaps in the current research and point to directions for future ABST research. Our results suggest that there is an interest in ABST after 1999 that resulted in the development of solutions using reactive, BDI, deliberative and cooperate agent architectures for software testing. In addition, most of the ABST approaches are designed using the JADE framework, have targeted the Java programming language, and are used at system-level testing for functional, non-functional and white-box testing. In regards to regression testing, our results indicate a research gap that could be addressed in future studies.
Learning from Data to Speed-up Sorted Table Search Procedures: Methodology and Practical Guidelines
Venue: arXiv cs.LG 2020
Year: 2020

Sorted Table Search Procedures are the quintessential query-answering tool, with widespread usage that now includes also Web Applications, e.g, Search Engines (Google Chrome) and ad Bidding Systems (AppNexus). Speeding them up, at very little cost in space, is still a quite significant achievement. Here we study to what extend Machine Learning Techniques can contribute to obtain such a speed-up via a systematic experimental comparison of known efficient implementations of Sorted Table Search procedures, with different Data Layouts, and their Learned counterparts developed here. We characterize the scenarios in which those latter can be profitably used with respect to the former, accounting for both CPU and GPU computing. Our approach contributes also to the study of Learned Data Structures, a recent proposal to improve the time/space performance of fundamental Data Structures, e.g., B-trees, Hash Tables, Bloom Filters. Indeed, we also formalize an Algorithmic Paradigm of Learned Dichotomic Sorted Table Search procedures that naturally complements the Learned one proposed here and that characterizes most of the known Sorted Table Search Procedures as having a "learning phase" that approximates Simple Linear Regression.
Inter-Homines: Distance-Based Risk Estimation for Human Safety
Venue: arXiv cs.CV 2020
Year: 2020

In this document, we report our proposal for modeling the risk of possible contagiousity in a given area monitored by RGB cameras where people freely move and interact. Our system, called Inter-Homines, evaluates in real-time the contagion risk in a monitored area by analyzing video streams: it is able to locate people in 3D space, calculate interpersonal distances and predict risk levels by building dynamic maps of the monitored area. Inter-Homines works both indoor and outdoor, in public and private crowded areas. The software is applicable to already installed cameras or low-cost cameras on industrial PCs, equipped with an additional embedded edge-AI system for temporary measurements. From the AI-side, we exploit a robust pipeline for real-time people detection and localization in the ground plane by homographic transformation based on state-of-the-art computer vision algorithms; it is a combination of a people detector and a pose estimator. From the risk modeling side, we propose a parametric model for a spatio-temporal dynamic risk estimation, that, validated by epidemiologists, could be useful for safety monitoring the acceptance of social distancing prevention measures by predicting the risk level of the scene.
On the Orbits of Automaton Semigroups and Groups
Venue: arXiv cs.FL 2020
Year: 2020

We investigate the orbits of automaton semigroups and groups to obtain algorithmic and structural results, both for general automata but also for some special subclasses. First, we show that a more general version of the finiteness problem for automaton groups is undecidable. This problem is equivalent to the finiteness problem for left principal ideals in automaton semigroups generated by complete and reversible automata. Then, we look at $ω$-word (i.e. right infinite words) with a finite orbit. We show that every automaton yielding an $ω$-word with a finite orbit already yields an ultimately periodic one, which is not periodic in general, however. On the algorithmic side, we observe that it is not possible to decide whether a given periodic $ω$-word has an infinite orbit and that we cannot check whether a given reversible and complete automaton admits an $ω$-word with a finite orbit, a reciprocal problem to the finiteness problem for automaton semigroups in the reversible case. Finally, we look at automaton groups generated by reversible but not bi-reversible automata and show that many words have infinite orbits under the action of such automata.
Complex Skill Acquisition Through Simple Skill Imitation Learning
Venue: arXiv cs.LG 2020
Year: 2020

Humans often think of complex tasks as combinations of simpler subtasks in order to learn those complex tasks more efficiently. For example, a backflip could be considered a combination of four subskills: jumping, tucking knees, rolling backwards, and thrusting arms downwards. Motivated by this line of reasoning, we propose a new algorithm that trains neural network policies on simple, easy-to-learn skills in order to cultivate latent spaces that accelerate imitation learning of complex, hard-to-learn skills. We focus on the case in which the complex task comprises a concurrent (and possibly sequential) combination of the simpler subtasks, and therefore our algorithm can be seen as a novel approach to concurrent hierarchical imitation learning. We evaluate our algorithm on difficult tasks in a high-dimensional environment and find that it consistently outperforms a state-of-the-art baseline in training speed and overall performance.
Relatable Clothing: Detecting Visual Relationships between People and Clothing
Venue: arXiv cs.CV 2020
Year: 2020

Detecting visual relationships between people and clothing in an image has been a relatively unexplored problem in the field of computer vision and biometrics. The lack readily available public dataset for ``worn'' and ``unworn'' classification has slowed the development of solutions for this problem. We present the release of the Relatable Clothing Dataset which contains 35287 person-clothing pairs and segmentation masks for the development of ``worn'' and ``unworn'' classification models. Additionally, we propose a novel soft attention unit for performing ``worn'' and ``unworn'' classification using deep neural networks. The proposed soft attention models have an accuracy of upward $98.55\% \pm 0.35\%$ on the Relatable Clothing Dataset and demonstrate high generalizable, allowing us to classify unseen articles of clothing such as high visibility vests as ``worn'' or ``unworn''.
Workflows in AiiDA: Engineering a high-throughput, event-based engine for robust and modular computational workflows
Venue: arXiv cs.DC 2020
Year: 2020

Over the last two decades, the field of computational science has seen a dramatic shift towards incorporating high-throughput computation and big-data analysis as fundamental pillars of the scientific discovery process. This has necessitated the development of tools and techniques to deal with the generation, storage and processing of large amounts of data. In this work we present an in-depth look at the workflow engine powering AiiDA, a widely adopted, highly flexible and database-backed informatics infrastructure with an emphasis on data reproducibility. We detail many of the design choices that were made which were informed by several important goals: the ability to scale from running on individual laptops up to high-performance supercomputers, managing jobs with runtimes spanning from fractions of a second to weeks and scaling up to thousands of jobs concurrently, and all this while maximising robustness. In short, AiiDA aims to be a Swiss army knife for high-throughput computational science. As well as the architecture, we outline important API design choices made to give workflow writers a great deal of liberty whilst guiding them towards writing robust and modular workflows, ultimately enabling them to encode their scientific knowledge to the benefit of the wider scientific community.
Phase Transition Behavior in Knowledge Compilation
Venue: arXiv cs.AI 2020
Year: 2020

The study of phase transition behaviour in SAT has led to deeper understanding and algorithmic improvements of modern SAT solvers. Motivated by these prior studies of phase transitions in SAT, we seek to study the behaviour of size and compile-time behaviour for random k-CNF formulas in the context of knowledge compilation. We perform a rigorous empirical study and analysis of the size and runtime behavior for different knowledge compilation forms (and their corresponding compilation algorithms): d-DNNFs, SDDs and OBDDs across multiple tools and compilation algorithms. We employ instances generated from the random k-CNF model with varying generation parameters to empirically reason about the expected and median behavior of size and compilation-time for these languages. Our work is similar in spirit to the early work in CSP community on phase transition behavior in SAT/CSP. In a similar spirit, we identify the interesting behavior with respect to different parameters: clause density and solution density, a novel control parameter that we identify for the study of phase transition behavior in the context of knowledge compilation. Furthermore, we summarize our empirical study in terms of two concrete conjectures; a rigorous study of these conjectures will possibly require new theoretical tools.
Visual Testing of GUIs by Abstraction
Venue: arXiv cs.SE 2020
Year: 2020

Ensuring the correct visual appearance of graphical user interfaces (GUIs) is important because visual bugs can cause substantial losses for businesses. An application might behave functionally correct in an automated test, but visual bugs can make the GUI effectively unusable for the user. Most of today's approaches for visual testing are pixel-based and tend to have flaws that are characteristic for image differencing. For instance, minor and unimportant visual changes often cause false positives, which confuse the user with unnecessary error reports. Our idea is to introduce an abstract GUI state (AGS), where we define structural relations to identify relevant GUI changes and ignore those that are unimportant from the user's point of view. In addition, we explore several strategies to address the GUI element identification problem in terms of AGS. This allows us to provide rich diagnostic information that help the user to better interpret changes. Based on the principles of golden master testing, we can support a fully-automated approach to visual testing by using the AGS. We have implemented our approach to visually test web pages and our experiments show that we are able to reliably detect GUI changes.
Unlocking the Potential of Deep Counterfactual Value Networks
Venue: arXiv cs.AI 2020
Year: 2020

Deep counterfactual value networks combined with continual resolving provide a way to conduct depth-limited search in imperfect-information games. However, since their introduction in the DeepStack poker AI, deep counterfactual value networks have not seen widespread adoption. In this paper we introduce several improvements to deep counterfactual value networks, as well as counterfactual regret minimization, and analyze the effects of each change. We combined these improvements to create the poker AI Supremus. We show that while a reimplementation of DeepStack loses head-to-head against the strong benchmark agent Slumbot, Supremus successfully beats Slumbot by an extremely large margin and also achieves a lower exploitability than DeepStack against a local best response. Together, these results show that with our key improvements, deep counterfactual value networks can achieve state-of-the-art performance.
Towards Ground Truth Explainability on Tabular Data
Venue: arXiv cs.LG 2020
Year: 2020

In data science, there is a long history of using synthetic data for method development, feature selection and feature engineering. Our current interest in synthetic data comes from recent work in explainability. Today's datasets are typically larger and more complex - requiring less interpretable models. In the setting of \textit{post hoc} explainability, there is no ground truth for explanations. Inspired by recent work in explaining image classifiers that does provide ground truth, we propose a similar solution for tabular data. Using copulas, a concise specification of the desired statistical properties of a dataset, users can build intuition around explainability using controlled data sets and experimentation. The current capabilities are demonstrated on three use cases: one dimensional logistic regression, impact of correlation from informative features, impact of correlation from redundant variables.
Online Carpooling using Expander Decompositions
Venue: arXiv cs.DS 2020
Year: 2020

We consider the online carpooling problem: given $n$ vertices, a sequence of edges arrive over time. When an edge $e_t = (u_t, v_t)$ arrives at time step $t$, the algorithm must orient the edge either as $v_t \rightarrow u_t$ or $u_t \rightarrow v_t$, with the objective of minimizing the maximum discrepancy of any vertex, i.e., the absolute difference between its in-degree and out-degree. Edges correspond to pairs of persons wanting to ride together, and orienting denotes designating the driver. The discrepancy objective then corresponds to every person driving close to their fair share of rides they participate in. In this paper, we design efficient algorithms which can maintain polylog$(n,T)$ maximum discrepancy (w.h.p) over any sequence of $T$ arrivals, when the arriving edges are sampled independently and uniformly from any given graph $G$. This provides the first polylogarithmic bounds for the online (stochastic) carpooling problem. Prior to this work, the best known bounds were $O(\sqrt{n \log n})$-discrepancy for any adversarial sequence of arrivals, or $O(\log\!\log n)$-discrepancy bounds for the stochastic arrivals when $G$ is the complete graph. The technical crux of our paper is in showing that the simple greedy algorithm, which has provably good discrepancy bounds when the arriving edges are drawn uniformly at random from the complete graph, also has polylog discrepancy when $G$ is an expander graph. We then combine this with known expander-decomposition results to design our overall algorithm.
Scalable Termination Detection for Distributed Actor Systems
Venue: arXiv cs.LO 2020
Year: 2020

Automatic garbage collection (GC) prevents certain kinds of bugs and reduces programming overhead. GC techniques for sequential programs are based on reachability analysis. However, testing reachability from a root set is inadequate for determining whether an actor is garbage because an unreachable actor may send a message to a reachable actor. Instead, it is sufficient to check termination (sometimes also called quiescence): an actor is terminated if it is not currently processing a message and cannot receive a message in the future. Moreover, many actor frameworks provide all actors with access to file I/O or external storage; without inspecting an actor's internal code, it is necessary to check that the actor has terminated to ensure that it may be garbage collected in these frameworks. Previous algorithms to detect actor garbage require coordination mechanisms such as causal message delivery or nonlocal monitoring of actors for mutation. Such coordination mechanisms adversely affect concurrency and are therefore expensive in distributed systems. We present a low-overhead reference listing technique (called DRL) for termination detection in actor systems. DRL is based on asynchronous local snapshots and message-passing between actors. This enables a decentralized implementation and transient network partition tolerance. The paper provides a formal description of DRL, shows that all actors identified as garbage have indeed terminated (safety), and that all terminated actors--under certain reasonable assumptions--will eventually be identified (liveness).
Explicit two-deletion codes with redundancy matching the existential bound
Venue: arXiv cs.IT 2020
Year: 2020

We give an explicit construction of length-$n$ binary codes capable of correcting the deletion of two bits that have size $2^n/n^{4+o(1)}$. This matches up to lower order terms the existential result, based on an inefficient greedy choice of codewords, that guarantees such codes of size $Ω(2^n/n^4)$. Our construction is based on augmenting the classic Varshamov-Tenengolts construction of single deletion codes with additional check equations. We also give an explicit construction of binary codes of size $Ω(2^n/n^{3+o(1)})$ that can be list decoded from two deletions using lists of size two. Previously, even the existence of such codes was not clear.