OpenRaiser/Intern-Atlas huggingface dataset:
On the Probability of Partial Decoding in Sparse Network Coding
Venue: arXiv cs.IT 2019
Year: 2019

Sparse Network Coding (SNC) has been a promising network coding scheme as an improvement for Random Linear Network Coding (RLNC) in terms of the computational complexity. However, in this literature, there has been no analytical expressions for the probability of decoding a fraction of source messages after transmission of some coded packets. In this work, we looked into the problem of the probability of decoding a fraction of source messages, i.e., partial decoding, in the decoder for a system which uses SNC. We exploited the Principle of Inclusion and Exclusion to derive expressions of partial decoding probability. The presented model predicts the probability of partial decoding with an average deviation of 6%. Our results show that SNC has a great potential for recovering a fraction of the source message, especially in higher sparsity and lower Galois Field size. Moreover, to achieve a better probability of partial decoding throughout transmissions, we define a sparsity tuning scheme that significantly increases the probability of partial decoding. Our results show that this tuning scheme achieves a 16% improvement in terms of probability of decoding a fraction of source packets with respect to traditional SNC.
TopicSifter: Interactive Search Space Reduction Through Targeted Topic Modeling
Venue: arXiv cs.IR 2019
Year: 2019

Topic modeling is commonly used to analyze and understand large document collections. However, in practice, users want to focus on specific aspects or "targets" rather than the entire corpus. For example, given a large collection of documents, users may want only a smaller subset which more closely aligns with their interests, tasks, and domains. In particular, our paper focuses on large-scale document retrieval with high recall where any missed relevant documents can be critical. A simple keyword matching search is generally not effective nor efficient as 1) it is difficult to find a list of keyword queries that can cover the documents of interest before exploring the dataset, 2) some documents may not contain the exact keywords of interest but may still be highly relevant, and 3) some words have multiple meanings, which would result in irrelevant documents included in the retrieved subset. In this paper, we present TopicSifter, a visual analytics system for interactive search space reduction. Our system utilizes targeted topic modeling based on nonnegative matrix factorization and allows users to give relevance feedback in order to refine their target and guide the topic modeling to the most relevant results.
Characterizing and Understanding Software Developer Networks in Security Development
Venue: arXiv cs.SE 2019
Year: 2019

To build secure software, developers often work together during software development and maintenance to find, fix, and prevent security vulnerabilities. Examining the nature of developer interactions during their security activities regarding security introducing and fixing activities can provide insights for improving current practices. In this work, we conduct a large-scale empirical study to characterize and understand developers' interactions during their security activities regarding security introducing and fixing, which involves more than 16K security fixing commits and over 28K security introducing commits from nine large-scale open-source software projects. For our analysis, we first examine whether a project is a hero-centric project when assessing developers' contribution in their security activities. Then we study the interaction patterns between developers, explore how the distribution of the patterns changes over time, and study the impact of developers' interactions on the quality of projects. In addition, we also characterize the nature of developer interaction in security activities in comparison to developer interaction in non-security activities (i.e., introducing and fixing non-security bugs). Among our findings we identify that: most of the experimental projects are non hero-centric projects when evaluating developers' contribution by using their security activities; there exist common dominating interaction patterns across our experimental projects; the distribution of interaction patterns has correlation with the quality of software projects. We believe the findings from this study can help developers understand how vulnerabilitiesoriginate and fix under the interactions of software developers.
A Proof of Concept SRAM-based Physically Unclonable Function (PUF) Key Generation Mechanism for IoT Devices
Venue: arXiv cs.CR 2019
Year: 2019

This paper provides a proof of concept for using SRAM based Physically Unclonable Functions (PUFs) to generate private keys for IoT devices. PUFs are utilized, as there is inadequate protection for secret keys stored in the memory of the IoT devices. We utilize a custom-made Arduino mega shield to extract the fingerprint from SRAM chip on demand. We utilize the concepts of ternary states to exclude the cells which are easily prone to flip, allowing us to extract stable bits from the fingerprint of the SRAM. Using the custom-made software for our SRAM device, we can control the error rate of the PUF to achieve an adjustable memory-based PUF for key generation. We utilize several fuzzy extractor techniques based on using different error correction coding methods to generate secret keys from the SRAM PUF, and study the trade-off between the false authentication rate and false rejection rate of the PUF.
Multi-modal Predictive Models of Diabetes Progression
Venue: arXiv cs.LG 2019
Year: 2019

With the increasing availability of wearable devices, continuous monitoring of individuals' physiological and behavioral patterns has become significantly more accessible. Access to these continuous patterns about individuals' statuses offers an unprecedented opportunity for studying complex diseases and health conditions such as type 2 diabetes (T2D). T2D is a widely common chronic disease that its roots and progression patterns are not fully understood. Predicting the progression of T2D can inform timely and more effective interventions to prevent or manage the disease. In this study, we have used a dataset related to 63 patients with T2D that includes the data from two different types of wearable devices worn by the patients: continuous glucose monitoring (CGM) devices and activity trackers (ActiGraphs). Using this dataset, we created a model for predicting the levels of four major biomarkers related to T2D after a one-year period. We developed a wide and deep neural network and used the data from the demographic information, lab tests, and wearable sensors to create the model. The deep part of our method was developed based on the long short-term memory (LSTM) structure to process the time-series dataset collected by the wearables. In predicting the patterns of the four biomarkers, we have obtained a root mean square error of 1.67% for HBA1c, 6.22 mg/dl for HDL cholesterol, 10.46 mg/dl for LDL cholesterol, and 18.38 mg/dl for Triglyceride. Compared to existing models for studying T2D, our model offers a more comprehensive tool for combining a large variety of factors that contribute to the disease.
On Observability and Monitoring of Distributed Systems: An Industry Interview Study
Venue: arXiv cs.DC 2019
Year: 2019

Business success of companies heavily depends on the availability and performance of their client applications. Due to modern development paradigms such as DevOps and microservice architectural styles, applications are decoupled into services with complex interactions and dependencies. Although these paradigms enable individual development cycles with reduced delivery times, they cause several challenges to manage the services in distributed systems. One major challenge is to observe and monitor such distributed systems. This paper provides a qualitative study to understand the challenges and good practices in the field of observability and monitoring of distributed systems. In 28 semi-structured interviews with software professionals we discovered increasing complexity and dynamics in that field. Especially observability becomes an essential prerequisite to ensure stable services and further development of client applications. However, the participants mentioned a discrepancy in the awareness regarding the importance of the topic, both from the management as well as from the developer perspective. Besides technical challenges, we identified a strong need for an organizational concept including strategy, roles and responsibilities. Our results support practitioners in developing and implementing systematic observability and monitoring for distributed systems.
Linear reconstructions and the analysis of the stable sampling rate
Venue: arXiv cs.IT 2019
Year: 2019

The theory of sampling and the reconstruction of data has a wide range of applications and a rich collection of techniques. For many methods a core problem is the estimation of the number of samples needed in order to secure a stable and accurate reconstruction. This can often be controlled by the Stable Sampling Rate (SSR). In this paper we discuss the SSR and how it is crucial for two key linear methods in sampling theory: generalized sampling and the recently developed Parametrized Background Data Weak (PBDW) method. Both of these approaches rely on estimates of the SSR in order to be accurate. In many areas of signal and image processing binary samples are crucial and such samples, which can be modelled by Walsh functions, are the core of our analysis. As we show, the SSR is linear when considering binary sampling with Walsh functions and wavelet reconstruction. Moreover, for certain wavelets it is possible to determine the SSR exactly, allowing sharp estimates for the performance of the methods.
Robust Cellular Communications for Unmanned Aerial Vehicles in Maritime Search and Rescue
Venue: arXiv cs.NI 2019
Year: 2019

Unmanned aerial vehicles (UAV) are a promising technology for fast, large scale survey operations such as maritime search and rescue (SAR). However, providing reliable communications over long distances remains a challenge. Cellular technology such as Long Term Evolution (LTE) is designed to perform well in the presence of fast-moving clients and highly dynamic channel conditions. Yet, its generic medium access mechanisms make it hard to support low-latency uplink traffic, which is needed for real-time command and control and similar applications. In this paper, we introduce an unmanned aerial system for maritime SAR, supported via an LTE data link. To mitigate drawbacks in uplink channel access, we develop a resource-guaranteed scheme based on persistent scheduling, using an open-source LTE stack. The approach is evaluated with a laboratory setup using software-defined radio modules. Measurements are taken on the application layer, using real-world telemetry data generated by an autopilot system in the presence of high bandwidth background traffic. Evaluations demonstrate that our system fulfills UAV requirements in terms of latency and reliability. Latency is further reduced to 6 ms on average and a 99.9th percentile of 10 ms by application-aware overprovisioning for mission-critical traffic and users.
Strengthening Gossip Protocols using Protocol-Dependent Knowledge
Venue: arXiv cs.LO 2019
Year: 2019

Distributed dynamic gossip is a generalization of the classic telephone problem in which agents communicate to share secrets, with the additional twist that also telephone numbers are exchanged to determine who can call whom. Recent work focused on the success conditions of simple protocols such as "Learn New Secrets" (LNS) wherein an agent a may only call another agent b if a does not know b's secret. A protocol execution is successful if all agents get to know all secrets. On partial networks these protocols sometimes fail because they ignore information available to the agents that would allow for better coordination. We study how epistemic protocols for dynamic gossip can be strengthened, using epistemic logic as a simple protocol language with a new operator for protocol-dependent knowledge. We provide definitions of different strengthenings and show that they perform better than LNS, but we also prove that there is no strengthening of LNS that always terminates successfully. Together, this gives us a better picture of when and how epistemic coordination can help in the dynamic gossip problem in particular and distributed systems in general.
A Join-Based Hybrid Parameter for Constraint Satisfaction
Venue: arXiv cs.DS 2019
Year: 2019

We propose joinwidth, a new complexity parameter for the Constraint Satisfaction Problem (CSP). The definition of joinwidth is based on the arrangement of basic operations on relations (joins, projections, and pruning), which inherently reflects the steps required to solve the instance. We use joinwidth to obtain polynomial-time algorithms (if a corresponding decomposition is provided in the input) as well as fixed-parameter algorithms (if no such decomposition is provided) for solving the CSP. Joinwidth is a hybrid parameter, as it takes both the graphical structure as well as the constraint relations that appear in the instance into account. It has, therefore, the potential to capture larger classes of tractable instances than purely structural parameters like hypertree width and the more general fractional hypertree width (fhtw). Indeed, we show that any class of instances of bounded fhtw also has bounded joinwidth, and that there exist classes of instances of bounded joinwidth and unbounded fhtw, so bounded joinwidth properly generalizes bounded fhtw. We further show that bounded joinwidth also properly generalizes several other known hybrid restrictions, such as fhtw with degree constraints and functional dependencies. In this sense, bounded joinwidth can be seen as a unifying principle that explains the tractability of several seemingly unrelated classes of CSP instances.
On the Value of Bandit Feedback for Offline Recommender System Evaluation
Venue: arXiv cs.IR 2019
Year: 2019

In academic literature, recommender systems are often evaluated on the task of next-item prediction. The procedure aims to give an answer to the question: "Given the natural sequence of user-item interactions up to time t, can we predict which item the user will interact with at time t+1?". Evaluation results obtained through said methodology are then used as a proxy to predict which system will perform better in an online setting. The online setting, however, poses a subtly different question: "Given the natural sequence of user-item interactions up to time t, can we get the user to interact with a recommended item at time t+1?". From a causal perspective, the system performs an intervention, and we want to measure its effect. Next-item prediction is often used as a fall-back objective when information about interventions and their effects (shown recommendations and whether they received a click) is unavailable. When this type of data is available, however, it can provide great value for reliably estimating online recommender system performance. Through a series of simulated experiments with the RecoGym environment, we show where traditional offline evaluation schemes fall short. Additionally, we show how so-called bandit feedback can be exploited for effective offline evaluation that more accurately reflects online performance.
Zero-Knowledge User Authentication: An Old Idea Whose Time Has Come
Venue: arXiv cs.CR 2019
Year: 2019

User authentication can rely on various factors (e.g., a password, a cryptographic key, biometric data) but should not reveal any secret or private information. This seemingly paradoxical feat can be achieved through zero-knowledge proofs. Unfortunately, naive password-based approaches still prevail on the web. Multi-factor authentication schemes address some of the weaknesses of the traditional login process, but generally have deployability issues or degrade usability even further as they assume users do not possess adequate hardware. This assumption no longer holds: smartphones with biometric sensors, cameras, short-range communication capabilities, and unlimited data plans have become ubiquitous. In this paper, we show that, assuming the user has such a device, both security and usability can be drastically improved using an augmented password-authenticated key agreement (PAKE) protocol and message authentication codes.
Learning abstract perceptual notions: the example of space
Venue: arXiv cs.AI 2019
Year: 2019

Humans are extremely swift learners. We are able to grasp highly abstract notions, whether they come from art perception or pure mathematics. Current machine learning techniques demonstrate astonishing results in extracting patterns in information. Yet the abstract notions we possess are more than just statistical patterns in the incoming information. Sensorimotor theory suggests that they represent functions, laws, describing how the information can be transformed, or, in other words, they represent the statistics of sensorimotor changes rather than sensory inputs themselves. The aim of our work is to suggest a way for machine learning and sensorimotor theory to benefit from each other so as to pave the way toward new horizons in learning. We show in this study that a highly abstract notion, that of space, can be seen as a collection of laws of transformations of sensory information and that these laws could in theory be learned by a naive agent. As an illustration we do a one-dimensional simulation in which an agent extracts spatial knowledge in the form of internalized ("sensible") rigid displacements. The agent uses them to encode its own displacements in a way which is isometrically related to external space. Though the algorithm allowing acquisition of rigid displacements is designed \emph{ad hoc}, we believe it can stimulate the development of unsupervised learning techniques leading to similar results.
A Syntactic Operator for Forgetting that Satisfies Strong Persistence
Venue: arXiv cs.AI 2019
Year: 2019

Whereas the operation of forgetting has recently seen a considerable amount of attention in the context of Answer Set Programming (ASP), most of it has focused on theoretical aspects, leaving the practical issues largely untouched. Recent studies include results about what sets of properties operators should satisfy, as well as the abstract characterization of several operators and their theoretical limits. However, no concrete operators have been investigated. In this paper, we address this issue by presenting the first concrete operator that satisfies strong persistence - a property that seems to best capture the essence of forgetting in the context of ASP - whenever this is possible, and many other important properties. The operator is syntactic, limiting the computation of the forgetting result to manipulating the rules in which the atoms to be forgotten occur, naturally yielding a forgetting result that is close to the original program. This paper is under consideration for acceptance in TPLP.
CerebroVis: Designing an Abstract yet Spatially Contextualized Cerebral Arteries Network Visualization
Venue: arXiv cs.HC 2019
Year: 2019

Blood circulation in the human brain is supplied through a network of cerebral arteries. If a clinician suspects a patient has a stroke or other cerebrovascular condition they order imaging tests. Neuroradiologists visually search the resulting scans for abnormalities. Their visual search tasks correspond to the abstract network analysis tasks of browsing and path following. To assist neuroradiologists in identifying cerebral artery abnormalities we designed CerebroVis, a novel abstract---yet spatially contextualized---cerebral artery network visualization. In this design study, we contribute a novel framing and definition of the cerebral artery system in terms of network theory and characterize neuroradiologist domain goals as abstract visualization and network analysis tasks. Through an iterative, user-centered design process we developed an abstract network layout technique which incorporates cerebral artery spatial context. The abstract visualization enables increased domain task performance over 3D geometry representations, while including spatial context helps preserve the user's mental map of the underlying geometry. We provide open source implementations of our network layout technique and prototype cerebral artery visualization tool. We demonstrate the robustness of our technique by successfully laying out 61 open source brain scans. We evaluate the effectiveness of our layout through a mixed methods study with three neuroradiologists. In a formative controlled experiment our study participants used CerebroVis and a conventional 3D visualization to examine real cerebral artery imaging data and to identify a simulated intracranial artery stenosis. Participants were more accurate at identifying stenoses using CerebroVis (absolute risk difference 13%). A free copy of this paper, the evaluation stimuli and data, and source code are available at https://osf.io/e5sxt/.
CUNI Systems for the Unsupervised News Translation Task in WMT 2019
Venue: arXiv cs.CL 2019
Year: 2019

In this paper we describe the CUNI translation system used for the unsupervised news shared task of the ACL 2019 Fourth Conference on Machine Translation (WMT19). We follow the strategy of Artexte et al. (2018b), creating a seed phrase-based system where the phrase table is initialized from cross-lingual embedding mappings trained on monolingual data, followed by a neural machine translation system trained on synthetic parallel data. The synthetic corpus was produced from a monolingual corpus by a tuned PBMT model refined through iterative back-translation. We further focus on the handling of named entities, i.e. the part of vocabulary where the cross-lingual embedding mapping suffers most. Our system reaches a BLEU score of 15.3 on the German-Czech WMT19 shared task.
Let's Make It Personal, A Challenge in Personalizing Medical Inter-Human Communication
Venue: arXiv cs.AI 2019
Year: 2019

Current AI approaches have frequently been used to help personalize many aspects of medical experiences and tailor them to a specific individuals' needs. However, while such systems consider medically-relevant information, they ignore socially-relevant information about how this diagnosis should be communicated and discussed with the patient. The lack of this capability may lead to mis-communication, resulting in serious implications, such as patients opting out of the best treatment. Consider a case in which the same treatment is proposed to two different individuals. The manner in which this treatment is mediated to each should be different, depending on the individual patient's history, knowledge, and mental state. While it is clear that this communication should be conveyed via a human medical expert and not a software-based system, humans are not always capable of considering all of the relevant aspects and traversing all available information. We pose the challenge of creating Intelligent Agents (IAs) to assist medical service providers (MSPs) and consumers in establishing a more personalized human-to-human dialogue. Personalizing conversations will enable patients and MSPs to reach a solution that is best for their particular situation, such that a relation of trust can be built and commitment to the outcome of the interaction is assured. We propose a four-part conceptual framework for personalized social interactions, expand on which techniques are available within current AI research and discuss what has yet to be achieved.