OpenRaiser/Intern-Atlas huggingface dataset:
IGLOO: Slicing the Features Space to Represent Sequences
Venue: arXiv cs.LG 2020
Year: 2020

Historically, Recurrent neural networks (RNNs) and its variants such as LSTM and GRU and more recently Transformers have been the standard go-to components when processing sequential data with neural networks. One notable issue is the relative difficulty to deal with long sequences (i.e. more than 20,000 steps). We introduce IGLOO, a new neural network architecture which aims at being efficient for short sequences but also at being able to deal with long sequences. IGLOOs core idea is to use the relationships between non-local patches sliced out of the features maps of successively applied convolutions to build a representation for the sequence. We show that the model can deal with dependencies of more than 20,000 steps in a reasonable time frame. We stress test IGLOO on the copy-memory and addition tasks, as well as permuted MNIST (98.4%). For a larger task we apply this new structure to the Wikitext-2 dataset Merity et al. (2017b) and achieve a perplexity in line with baseline Transformers but lower than baseline AWD-LSTM. We also present how IGLOO is already used today in production for bioinformatics tasks.
Causal Discovery in the Presence of Missing Data
Venue: arXiv cs.LG 2020
Year: 2020

Missing data are ubiquitous in many domains including healthcare. When these data entries are not missing completely at random, the (conditional) independence relations in the observed data may be different from those in the complete data generated by the underlying causal process. Consequently, simply applying existing causal discovery methods to the observed data may lead to wrong conclusions. In this paper, we aim at developing a causal discovery method to recover the underlying causal structure from observed data that follow different missingness mechanisms, including missing completely at random (MCAR), missing at random (MAR), and missing not at random (MNAR). With missingness mechanisms represented by missingness graphs, we analyse conditions under which additional correction is needed to derive conditional independence/dependence relations in the complete data. Based on our analysis, we propose the Missing Value PC (MVPC) algorithm for both continuous and binary variables, which extends the PC algorithm to incorporate additional corrections. Our proposed MVPC is shown in theory to give asymptotically correct results even on data that are MAR or MNAR. Experimental results on synthetic data show that the proposed algorithm is able to find correct causal relations even in the general case of MNAR. Moreover, we create a neuropathic pain diagnostic simulator for evaluating causal discovery methods. Evaluated on such simulated neuropathic pain diagnosis records and the other two real world applications, MVPC outperforms the other benchmark methods.
On nested code pairs from the Hermitian curve
Venue: arXiv cs.IT 2020
Year: 2020

Nested code pairs play a crucial role in the construction of ramp secret sharing schemes [Kurihara et al. 2012] and in the CSS construction of quantum codes [Ketkar et al. 2006]. The important parameters are (1) the codimension, (2) the relative minimum distance of the codes, and (3) the relative minimum distance of the dual set of codes. Given values for two of them, one aims at finding a set of nested codes having parameters with these values and with the remaining parameter being as large as possible. In this work we study nested codes from the Hermitian curve. For not too small codimension, we present improved constructions and provide closed formula estimates on their performance. For small codimension we show how to choose pairs of one-point algebraic geometric codes in such a way that one of the relative minimum distances is larger than the corresponding non-relative minimum distance.
In Praise of Impredicativity: A Contribution to the Formalisation of Meta-Programming
Venue: arXiv cs.LO 2020
Year: 2020

Processing programs as data is one of the successes of functional and logic programming. Higher-order functions, as program-processing programs are called in functional programming, and meta-programs, as they are called in logic programming, are widespread declarative programming techniques. In logic programming, there is a gap between the meta-programming practice and its theory: The formalisations of meta-programming do not explicitly address its impredicativity and are not fully adequate. This article aims at overcoming this unsatisfactory situation by discussing the relevance of impredicativity to meta-programming, by revisiting former formalisations of meta-programming and by defining Reflective Predicate Logic, a conservative extension of first-order logic, which provides a simple formalisation of meta-programming.
Identifying Position-Dependent Mechanical Systems: A Modal Approach Applied to a Flexible Wafer Stage
Venue: arXiv cs.SY 2020
Year: 2020

Increasingly stringent performance requirements for motion control necessitate the use of increasingly detailed models of the system behavior. Motion systems inherently move, therefore, spatio-temporal models of the flexible dynamics are essential. In this paper, a two-step approach for the identification of the spatio-temporal behavior of mechanical systems is developed and applied to a lightweight prototype industrial wafer stage. The proposed approach exploits a modal modeling framework and combines recently developed powerful linear time invariant (LTI) identification tools with a spline-based mode-shape interpolation approach to estimate the spatial system behavior. The experimental results for the wafer stage application confirm the suitability of the proposed approach for the identification of complex position-dependent mechanical systems, and its potential for motion control performance improvements.
Imparting Interpretability to Word Embeddings while Preserving Semantic Structure
Venue: arXiv cs.CL 2020
Year: 2020

As an ubiquitous method in natural language processing, word embeddings are extensively employed to map semantic properties of words into a dense vector representation. They capture semantic and syntactic relations among words but the vectors corresponding to the words are only meaningful relative to each other. Neither the vector nor its dimensions have any absolute, interpretable meaning. We introduce an additive modification to the objective function of the embedding learning algorithm that encourages the embedding vectors of words that are semantically related to a predefined concept to take larger values along a specified dimension, while leaving the original semantic learning mechanism mostly unaffected. In other words, we align words that are already determined to be related, along predefined concepts. Therefore, we impart interpretability to the word embedding by assigning meaning to its vector dimensions. The predefined concepts are derived from an external lexical resource, which in this paper is chosen as Roget's Thesaurus. We observe that alignment along the chosen concepts is not limited to words in the Thesaurus and extends to other related words as well. We quantify the extent of interpretability and assignment of meaning from our experimental results. Manual human evaluation results have also been presented to further verify that the proposed method increases interpretability. We also demonstrate the preservation of semantic coherence of the resulting vector space by using word-analogy and word-similarity tests. These tests show that the interpretability-imparted word embeddings that are obtained by the proposed framework do not sacrifice performances in common benchmark tests.
A Swarming Approach to Optimize the One-hop Delay in Smart Driving Inter-platoon Communications
Venue: arXiv cs.NI 2020
Year: 2020

In this paper, we propose a swarming approach and optimize the one-hop delay for interplatoon communications through adjusting the minimum contention window size of each backbone vehicle in two steps. In the first step, we first set a small enough average one-hop delay as the initial optimization goal and then propose a swarming approach to find a minimum average one-hop delay for inter-platoon communications through adjusting the minimum contention window of each backbone vehicle iteratively. In the second step, we first set the minimum average one-hop delay found in the first step as the initial optimization goal and then adopt the swarming approach again to get the one-hop delay of each backbone vehicle balance to the minimum average one-hop delay. The optimal minimum contention window sizes that get the one-hop delay of each backbone vehicle balance to the minimum average one-hop delay are obtained after the second step. The simulation results indicate that the one-hop delay is optimized and the other performance metrics including end-to-end delay, one-hop throughput and transmission probability are presented by using the optimal minimum contention window sizes.
Spacetime-Entangled Networks (I) Relativity and Observability of Stepwise Consensus
Venue: arXiv cs.DC 2020
Year: 2020

Consensus protocols can be an effective tool for synchronizing small amounts of data over small regions. We describe the concept and implementation of entangled links, applied to data transmission, using the framework of Promise Theory as a tool to help bring certainty to distributed consensus. Entanglement describes co-dependent evolution of state. Networks formed by entanglement of agents keep certain promises: they deliver sequential messages, end-to-end, in order, and with atomic confirmation of delivery to both ends of the link. These properties can be used recursively to assure a hierarchy of conditional promises at any scale. This is a useful property where a consensus of state or `common knowledge' is required. We intentionally straddle theory and implementation in this discussion.
On L-shaped point set embeddings of trees: first non-embeddable examples
Venue: arXiv cs.CG 2020
Year: 2020

An L-shaped embedding of a tree in a point set is a planar drawing of the tree where the vertices are mapped to distinct points and every edge is drawn as a sequence of two axis-aligned line segments. There has been considerable work on establishing upper bounds on the minimum cardinality of a point set to guarantee that any tree of the same size with maximum degree 4 admits an L-shaped embedding on the point set. However, no non-trivial lower bound is known to this date, i.e., no known $n$-vertex tree requires more than $n$ points to be embedded. In this paper, we present the first examples of $n$-vertex trees for $n\in\{13,14,16,17,18,19,20\}$ that require strictly more points than vertices to admit an L-shaped embedding. Moreover, using computer help, we show that every tree on $n\leq 12$ vertices admits an L-shaped embedding in every set of $n$ points. We also consider embedding ordered trees, where the cyclic order of the neighbors of each vertex in the embedding is prescribed. For this setting, we determine the smallest non-embeddable ordered tree on $n=10$ vertices, and we show that every ordered tree on $n\leq 9$ or $n=11$ vertices admits an L-shaped embedding in every set of $n$ points. We also construct an infinite family of ordered trees which do not always admit an L-shaped embedding, answering a question raised by Biedl, Chan, Derka, Jain, and Lubiw.
TREVERSE: Trial-and-Error Lightweight Secure Reverse Authentication with Simulatable PUFs
Venue: arXiv cs.CR 2020
Year: 2020

A physical unclonable function (PUF) generates hardware intrinsic volatile secrets by exploiting uncontrollable manufacturing randomness. Although PUFs provide the potential for lightweight and secure authentication for increasing numbers of low-end Internet of Things devices, practical and secure mechanisms remain elusive. We aim to explore simulatable PUFs (SimPUFs) that are physically unclonable but efficiently modeled mathematically through privileged one-time PUF access to address the above problem. Given a challenge, a securely stored SimPUF in possession of a trusted server computes the corresponding response and its bit-specific reliability. Consequently, naturally noisy PUF responses generated by a resource limited prover can be immediately processed by a one-way function (OWF) and transmitted to the server, because the resourceful server can exploit the SimPUF to perform a trial-and-error search over likely error patterns to recover the noisy response to authenticate the prover. Security of trial-and-error reverse (TREVERSE) authentication under the random oracle model is guaranteed by the hardness of inverting the OWF. We formally evaluate the TREVERSE authentication capability with two SimPUFs experimentally derived from popular silicon PUFs.
The Effects of Visual and Control Latency on Piloting a Quadcopter using a Head-Mounted Display
Venue: arXiv cs.HC 2020
Year: 2020

Recent research has proposed teleoperation of robotic and aerial vehicles using head motion tracked by a head-mounted display (HMD). First-person views of the vehicles are usually captured by onboard cameras and presented to users through the display panels of HMDs. This provides users with a direct, immersive and intuitive interface for viewing and control. However, a typically overlooked factor in such designs is the latency introduced by the vehicle dynamics. As head motion is coupled with visual updates in such applications, visual and control latency always exists between the issue of control commands by head movements and the visual feedback received at the completion of the attitude adjustment. This causes a discrepancy between the intended motion, the vestibular cue and the visual cue and may potentially result in simulator sickness. No research has been conducted on how various levels of visual and control latency introduced by dynamics in robots or aerial vehicles affect users' performance and the degree of simulator sickness elicited. Thus, it is uncertain how much performance is degraded by latency and whether such designs are comfortable from the perspective of users. To address these issues, we studied a prototyped scenario of a head motion controlled quadcopter using an HMD. We present a virtual reality (VR) paradigm to systematically assess the effects of visual and control latency in simulated drone control scenarios.
Robust Pricing with Refunds
Venue: arXiv cs.GT 2020
Year: 2020

Before purchase, a buyer of an experience good learns about the product's fit using various information sources, including some of which the seller may be unaware of. The buyer, however, can conclusively learn the fit only after purchasing and trying out the product. We show that the seller can use a simple mechanism to best take advantage of the buyer's post-purchase learning to maximize his guaranteed-profit. We show that this mechanism combines a generous refund, which performs well when the buyer is relatively informed, with non-refundable random discounts, which work well when the buyer is relatively uninformed.
Positive 1-in-3-SAT admits a non-trivial Kernel
Venue: arXiv cs.CC 2020
Year: 2020

We illustrate the strength of Algebraic Methods, adapting Gaussian Elimination and Substitution to the problem of Exact Boolean Satisfiability. For 1-in-3 SAT with non-negated literals we are able to obtain considerably smaller equivalent instances of 0/1 Integer Programming restricted to Equality only. Both Gaussian Elimination and Substitution may be used in a processing step, followed by a type of brute-force approach on the kernel thus obtained. Our method shows that Positive instances of 1-in-3 SAT may be reduced to significantly smaller instances of I.P.E. in the following sense. Any such instance of $|V|$ variables and $|C|$ clauses can be polynomial-time reduced to an instance of 0/1 Integer Programming with Equality, of size at most $2/3|V|$ variables and at most $|C|$ clauses. We obtain an upper bound for the complexity of counting, $O(2κr 2^{(1-κ) r})$ for number of variables $r$ and clauses to variables ratio $κ$. We proceed to define formally the notion of a non-trivial kernel, defining the problems considered as Constraint Satisfaction Problems. We conclude showing the methods presented here, giving a non-trivial kernel for positive 1-in-3 SAT, imply the existence of a non-trivial kernel for 1-in-3 SAT.
Hard to Solve Instances of the Euclidean Traveling Salesman Problem
Venue: arXiv cs.DM 2020
Year: 2020

The well known $4/3$ conjecture states that the integrality ratio of the subtour LP is at most $4/3$ for metric Traveling Salesman instances. We present a family of Euclidean Traveling Salesman instances for which we prove that the integrality ratio of the subtour LP converges to $4/3$. These instances (using the rounded Euclidean norm) turn out to be hard to solve exactly with Concorde, the fastest existing exact TSP solver. For a 200 vertex instance from our family of Euclidean Traveling Salesman instances Concorde needs several days of CPU time. This is more than 1,000,000 times the runtime for a TSPLIB instance of similar size. Thus our new family of Euclidean Traveling Salesman instances may serve as new benchmark instances for TSP algorithms.
A Simple Network of Nodes Moving on the Circle
Venue: arXiv cs.IT 2020
Year: 2020

Two simple Markov processes are examined, one in discrete and one in continuous time, arising from idealized versions of a transmission protocol for mobile, delay-tolerant networks. We consider two independent walkers moving with constant speed on either the discrete or continuous circle, and changing directions at independent geometric (respectively, exponential) times. One of the walkers carries a message that wishes to travel as far and as fast as possible in the clockwise direction. The message stays with its current carrier unless the two walkers meet, the carrier is moving counter-clockwise, and the other walker is moving clockwise. In that case, the message jumps to the other walker. The long-term average clockwise speed of the message is computed. An explicit expression is derived via the solution of an associated boundary value problem in terms of the generator of the underlying Markov process. The average transmission cost is also similarly computed, measured as the long-term number of jumps the message makes per unit time. The tradeoff between speed and cost is examined, as a function of the underlying problem parameters.
Characterization of Group-Strategyproof Mechanisms for Facility Location in Strictly Convex Space
Venue: arXiv cs.GT 2020
Year: 2020

We characterize the class of group-strategyproof mechanisms for the single facility location game in any unconstrained strictly convex space. A mechanism is \emph{group-strategyproof}, if no group of agents can misreport so that all its members are \emph{strictly} better off. A strictly convex space is a normed vector space where $\|x+y\|<2$ holds for any pair of different unit vectors $x \neq y$, e.g., any $L_p$ space with $p\in (1,\infty)$. We show that any deterministic, unanimous, group-strategyproof mechanism must be dictatorial, and that any randomized, unanimous, translation-invariant, group-strategyproof mechanism must be \emph{2-dictatorial}. Here a randomized mechanism is 2-dictatorial if the lottery output of the mechanism must be distributed on the line segment between two dictators' inputs. A mechanism is translation-invariant if the output of the mechanism follows the same translation of the input. Our characterization directly implies that any (randomized) translation-invariant approximation algorithm satisfying the group-strategyproofness property has a lower bound of $2$-approximation for maximum cost (whenever $n \geq 3$), and $n/2 - 1$ for social cost. We also find an algorithm that $2$-approximates the maximum cost and $n/2$-approximates the social cost, proving the bounds to be (almost) tight.
Multimodal Interaction-aware Motion Prediction for Autonomous Street Crossing
Venue: arXiv cs.RO 2020
Year: 2020

For mobile robots navigating on sidewalks, it is essential to be able to safely cross street intersections. Most existing approaches rely on the recognition of the traffic light signal to make an informed crossing decision. Although these approaches have been crucial enablers for urban navigation, the capabilities of robots employing such approaches are still limited to navigating only on streets containing signalized intersections. In this paper, we address this challenge and propose a multimodal convolutional neural network framework to predict the safety of a street intersection for crossing. Our architecture consists of two subnetworks; an interaction-aware trajectory estimation stream IA-TCNN, that predicts the future states of all observed traffic participants in the scene, and a traffic light recognition stream AtteNet. Our IA-TCNN utilizes dilated causal convolutions to model the behavior of the observable dynamic agents in the scene without explicitly assigning priorities to the interactions among them. While AtteNet utilizes Squeeze-Excitation blocks to learn a content-aware mechanism for selecting the relevant features from the data, thereby improving the noise robustness. Learned representations from the traffic light recognition stream are fused with the estimated trajectories from the motion prediction stream to learn the crossing decision. Furthermore, we extend our previously introduced Freiburg Street Crossing dataset with sequences captured at different types of intersections, demonstrating complex interactions among the traffic participants. Extensive experimental evaluations on public benchmark datasets and our proposed dataset demonstrate that our network achieves state-of-the-art performance for each of the subtasks, as well as for the crossing safety prediction.
Exploring Author Gender in Book Rating and Recommendation
Venue: arXiv cs.IR 2020
Year: 2020

Collaborative filtering algorithms find useful patterns in rating and consumption data and exploit these patterns to guide users to good items. Many of the patterns in rating datasets reflect important real-world differences between the various users and items in the data; other patterns may be irrelevant or possibly undesirable for social or ethical reasons, particularly if they reflect undesired discrimination, such as discrimination in publishing or purchasing against authors who are women or ethnic minorities. In this work, we examine the response of collaborative filtering recommender algorithms to the distribution of their input data with respect to a dimension of social concern, namely content creator gender. Using publicly-available book ratings data, we measure the distribution of the genders of the authors of books in user rating profiles and recommendation lists produced from this data. We find that common collaborative filtering algorithms differ in the gender distribution of their recommendation lists, and in the relationship of that output distribution to user profile distribution.