OpenRaiser/Intern-Atlas huggingface dataset:
Extending some results on the second neighborhood conjecture
Venue: arXiv cs.DM 2021
Year: 2021

A vertex in a directed graph is said to have a large second neighborhood if it has at least as many second out-neighbors as out-neighbors. The Second Neighborhood Conjecture, first stated by Seymour, asserts that there is a vertex having a large second neighborhood in every oriented graph (a directed graph without loops or digons). We prove that oriented graphs whose missing edges can be partitioned into a (possibly empty) matching and a (possibly empty) star satisfy this conjecture. This generalizes a result of Fidler and Yuster. An implication of our result is that every oriented graph without a sink and whose missing edges form a (possibly empty) matching has at least two vertices with large second neighborhoods. This is a strengthening of a theorem of Havet and Thomasse, who showed that the same holds for tournaments without a sink. Moreover, we also show that the conjecture is true for oriented graphs whose vertex set can be partitioned into an independent set and a 2-degenerate graph.
Measuring Market Performance with Stochastic Demand: Price of Anarchy and Price of Uncertainty
Venue: arXiv cs.GT 2021
Year: 2021

Globally operating suppliers face the rising challenge of wholesale pricing under scarce data about retail demand, in contrast to better informed, locally operating retailers. At the same time, as local businesses proliferate, markets congest and retail competition increases. To capture these strategic considerations, we employ the classic Cournot model and extend it to a two-stage supply chain with an upstream supplier who operates under demand uncertainty and multiple downstream retailers who compete over quantity. The supplier's belief about retail demand is modeled via a continuous probability distribution function F. If F has the decreasing generalized mean residual life property, then the supplier's optimal pricing policy exists and is the unique fixed point of the mean residual life function. We evaluate the realized Price of Uncertainty and show that there exist demand levels for which market performs better when the supplier prices under demand uncertainty. In general, performance worsens for lower values of realized demand. We examine the effects of increasing competition on supply chain efficiency via the realized Price of Anarchy and complement our findings with numerical results.
Ontology Reasoning with Deep Neural Networks
Venue: arXiv cs.AI 2021
Year: 2021

The ability to conduct logical reasoning is a fundamental aspect of intelligent human behavior, and thus an important problem along the way to human-level artificial intelligence. Traditionally, logic-based symbolic methods from the field of knowledge representation and reasoning have been used to equip agents with capabilities that resemble human logical reasoning qualities. More recently, however, there has been an increasing interest in using machine learning rather than logic-based symbolic formalisms to tackle these tasks. In this paper, we employ state-of-the-art methods for training deep neural networks to devise a novel model that is able to learn how to effectively perform logical reasoning in the form of basic ontology reasoning. This is an important and at the same time very natural logical reasoning task, which is why the presented approach is applicable to a plethora of important real-world problems. We present the outcomes of several experiments, which show that our model is able to learn to perform highly accurate ontology reasoning on very large, diverse, and challenging benchmarks. Furthermore, it turned out that the suggested approach suffers much less from different obstacles that prohibit logic-based symbolic reasoning, and, at the same time, is surprisingly plausible from a biological point of view.
Under the Hood: Using Diagnostic Classifiers to Investigate and Improve how Language Models Track Agreement Information
Venue: arXiv cs.CL 2021
Year: 2021

How do neural language models keep track of number agreement between subject and verb? We show that `diagnostic classifiers', trained to predict number from the internal states of a language model, provide a detailed understanding of how, when, and where this information is represented. Moreover, they give us insight into when and where number information is corrupted in cases where the language model ends up making agreement errors. To demonstrate the causal role played by the representations we find, we then use agreement information to influence the course of the LSTM during the processing of difficult sentences. Results from such an intervention reveal a large increase in the language model's accuracy. Together, these results show that diagnostic classifiers give us an unrivalled detailed look into the representation of linguistic information in neural models, and demonstrate that this knowledge can be used to improve their performance.
MVOR: A Multi-view RGB-D Operating Room Dataset for 2D and 3D Human Pose Estimation
Venue: arXiv cs.CV 2021
Year: 2021

Person detection and pose estimation is a key requirement to develop intelligent context-aware assistance systems. To foster the development of human pose estimation methods and their applications in the Operating Room (OR), we release the Multi-View Operating Room (MVOR) dataset, the first public dataset recorded during real clinical interventions. It consists of 732 synchronized multi-view frames recorded by three RGB-D cameras in a hybrid OR. It also includes the visual challenges present in such environments, such as occlusions and clutter. We provide camera calibration parameters, color and depth frames, human bounding boxes, and 2D/3D pose annotations. In this paper, we present the dataset, its annotations, as well as baseline results from several recent person detection and 2D/3D pose estimation methods. Since we need to blur some parts of the images to hide identity and nudity in the released dataset, we also present a comparative study of how the baselines have been impacted by the blurring. Results show a large margin for improvement and suggest that the MVOR dataset can be useful to compare the performance of the different methods.
Multiplayer bandits without observing collision information
Venue: arXiv cs.LG 2021
Year: 2021

We study multiplayer stochastic multi-armed bandit problems in which the players cannot communicate and if two or more players pull the same arm, a collision occurs and the involved players receive zero reward. We consider two feedback models: a model in which the players can observe whether a collision has occurred and a more difficult setup when no collision information is available. We give the first theoretical guarantees for the second model: an algorithm with a logarithmic regret, and an algorithm with a square-root regret type that does not depend on the gaps between the means. For the first model, we give the first square-root regret bounds that do not depend on the gaps. Building on these ideas, we also give an algorithm for reaching approximate Nash equilibria quickly in stochastic anti-coordination games.
Paraphrases as Foreign Languages in Multilingual Neural Machine Translation
Venue: arXiv cs.CL 2021
Year: 2021

Paraphrases, the rewordings of the same semantic meaning, are useful for improving generalization and translation. However, prior works only explore paraphrases at the word or phrase level, not at the sentence or corpus level. Unlike previous works that only explore paraphrases at the word or phrase level, we use different translations of the whole training data that are consistent in structure as paraphrases at the corpus level. We train on parallel paraphrases in multiple languages from various sources. We treat paraphrases as foreign languages, tag source sentences with paraphrase labels, and train on parallel paraphrases in the style of multilingual Neural Machine Translation (NMT). Our multi-paraphrase NMT that trains only on two languages outperforms the multilingual baselines. Adding paraphrases improves the rare word translation and increases entropy and diversity in lexical choice. Adding the source paraphrases boosts performance better than adding the target ones. Combining both the source and the target paraphrases lifts performance further; combining paraphrases with multilingual data helps but has mixed performance. We achieve a BLEU score of 57.2 for French-to-English translation using 24 corpus-level paraphrases of the Bible, which outperforms the multilingual baselines and is +34.7 above the single-source single-target NMT baseline.
Towards Tight Approximation Bounds for Graph Diameter and Eccentricities
Venue: arXiv cs.DS 2021
Year: 2021

Among the most important graph parameters is the Diameter, the largest distance between any two vertices. There are no known very efficient algorithms for computing the Diameter exactly. Thus, much research has been devoted to how fast this parameter can be approximated. Chechik et al. showed that the diameter can be approximated within a multiplicative factor of $3/2$ in $\tilde{O}(m^{3/2})$ time. Furthermore, Roditty and Vassilevska W. showed that unless the Strong Exponential Time Hypothesis (SETH) fails, no $O(n^{2-ε})$ time algorithm can achieve an approximation factor better than $3/2$ in sparse graphs. Thus the above algorithm is essentially optimal for sparse graphs for approximation factors less than $3/2$. It was, however, completely plausible that a $3/2$-approximation is possible in linear time. In this work we conditionally rule out such a possibility by showing that unless SETH fails no $O(m^{3/2-ε})$ time algorithm can achieve an approximation factor better than $5/3$. Another fundamental set of graph parameters are the Eccentricities. The Eccentricity of a vertex $v$ is the distance between $v$ and the farthest vertex from $v$. Chechik et al. showed that the Eccentricities of all vertices can be approximated within a factor of $5/3$ in $\tilde{O}(m^{3/2})$ time and Abboud et al. showed that no $O(n^{2-ε})$ algorithm can achieve better than $5/3$ approximation in sparse graphs. We show that the runtime of the $5/3$ approximation algorithm is also optimal under SETH. We also show that no near-linear time algorithm can achieve a better than $2$ approximation for the Eccentricities and that this is essentially tight: we give an algorithm that approximates Eccentricities within a $2+δ$ factor in $\tilde{O}(m/δ)$ time for any $0<δ<1$. This beats all Eccentricity algorithms in Cairo et al.
Robust, Expressive, and Quantitative Linear Temporal Logics: Pick any Two for Free (full version)
Venue: arXiv cs.LO 2021
Year: 2021

Linear Temporal Logic (LTL) is the standard specification language for reactive systems and is successfully applied in industrial settings. However, many shortcomings of LTL have been identified in the literature, among them the limited expressiveness, the lack of quantitative features, and the inability to express robustness. There is work on overcoming these shortcomings, but each of these is typically addressed in isolation. This is insufficient for applications where all shortcomings manifest themselves simultaneously. Here, we tackle this issue by introducing logics that address more than one shortcoming. To this end, we combine the logics Linear Dynamic Logic, Prompt-LTL, and robust LTL, each addressing one aspect, to new logics. For all combinations of two aspects, the resulting logic has the same desirable algorithmic properties as plain LTL. In particular, the highly efficient algorithmic backends that have been developed for LTL are also applicable to these new logics. Finally, we discuss how to address all three aspects simultaneously.
Streaming dictionary matching with mismatches
Venue: arXiv cs.DS 2021
Year: 2021

In the $k$-mismatch problem we are given a pattern of length $n$ and a text and must find all locations where the Hamming distance between the pattern and the text is at most $k$. A series of recent breakthroughs have resulted in an ultra-efficient streaming algorithm for this problem that requires only $O(k \log \frac{n}{k})$ space and $O(\log \frac{n}{k} (\sqrt{k \log k} + \log^3 n))$ time per letter [Clifford, Kociumaka, Porat, SODA 2019]. In this work, we consider a strictly harder problem called dictionary matching with $k$ mismatches. In this problem, we are given a dictionary of $d$ patterns, where the length of each pattern is at most $n$, and must find all substrings of the text that are within Hamming distance $k$ from one of the patterns. We develop a streaming algorithm for this problem with $O(k d \log^k d \mathrm{polylog}(n))$ space and $O(k \log^{k} d \mathrm{polylog}(n) + |\mathrm{occ}|)$ time per position of the text. The algorithm is randomised and outputs correct answers with high probability. On the lower bound side, we show that any streaming algorithm for dictionary matching with $k$ mismatches requires $Ω(k d)$ bits of space.
Universal Multi-Party Poisoning Attacks
Venue: arXiv cs.LG 2021
Year: 2021

In this work, we demonstrate universal multi-party poisoning attacks that adapt and apply to any multi-party learning process with arbitrary interaction pattern between the parties. More generally, we introduce and study $(k,p)$-poisoning attacks in which an adversary controls $k\in[m]$ of the parties, and for each corrupted party $P_i$, the adversary submits some poisoned data $\mathcal{T}'_i$ on behalf of $P_i$ that is still ``$(1-p)$-close'' to the correct data $\mathcal{T}_i$ (e.g., $1-p$ fraction of $\mathcal{T}'_i$ is still honestly generated). We prove that for any ``bad'' property $B$ of the final trained hypothesis $h$ (e.g., $h$ failing on a particular test example or having ``large'' risk) that has an arbitrarily small constant probability of happening without the attack, there always is a $(k,p)$-poisoning attack that increases the probability of $B$ from $μ$ to by $μ^{1-p \cdot k/m} = μ+ Ω(p \cdot k/m)$. Our attack only uses clean labels, and it is online. More generally, we prove that for any bounded function $f(x_1,\dots,x_n) \in [0,1]$ defined over an $n$-step random process $\mathbf{X} = (x_1,\dots,x_n)$, an adversary who can override each of the $n$ blocks with even dependent probability $p$ can increase the expected output by at least $Ω(p \cdot \mathrm{Var}[f(\mathbf{x})])$.
Whisper: Fast Flooding for Low-Power Wireless Networks
Venue: arXiv cs.NI 2021
Year: 2021

This paper presents Whisper, a fast and reliable protocol to flood small amounts of data into a multi-hop network. Whisper makes use of synchronous transmissions, a technique first introduced by the Glossy flooding protocol. In contrast to Glossy, Whisper does not let the radio switch from receive to transmit mode between messages. Instead, it makes nodes continuously transmit identical copies of the message and eliminates the gaps between subsequent transmissions. To this end, Whisper embeds the message to be flooded into a signaling packet that is composed of multiple packlets -- where a packlet is a portion of the message payload that mimics the structure of an actual packet. A node must intercept only one of the packlets to detect that there is an ongoing transmission and that it should start forwarding the message. This allows Whisper to speed up the propagation of the flood, and thus, to reduce the overall radio-on time of the nodes. Our evaluation on the FlockLab testbed shows that Whisper achieves comparable reliability but 2x lower radio-on time than Glossy. We further show that by embedding Whisper in an existing data collection application, we can more than double the lifetime of the network.
On learning an interpreted language with recurrent models
Venue: arXiv cs.CL 2021
Year: 2021

Can recurrent neural nets, inspired by human sequential data processing, learn to understand language? We construct simplified datasets reflecting core properties of natural language as modeled in formal syntax and semantics: recursive syntactic structure and compositionality. We find LSTM and GRU networks to generalise to compositional interpretation well, but only in the most favorable learning settings, with a well-paced curriculum, extensive training data, and left-to-right (but not right-to-left) composition.
Investigating Crowd Creativity in Online Music Communities
Venue: arXiv cs.HC 2021
Year: 2021

Crowd creativity is typically associated with peer-production communities focusing on artistic products like animations, video games, and music, but less frequently to Open Source Software (OSS), despite the fact that also developers must be creative to come up with new solutions to their technical challenges. In this paper, we conduct a study to further the understanding of which factors from prior work in both OSS and art communities are predictive of successful collaboration - defined as reuse of previous songs - in three different songwriting communities, namely Songtree, Splice, and ccMixter. The main findings from this study confirm that the success of collaborations is associated with high community status of recognizable authors and low degree of derivativity of songs.
Deep Knowledge Tracing and Dynamic Student Classification for Knowledge Tracing
Venue: arXiv cs.AI 2021
Year: 2021

In Intelligent Tutoring System (ITS), tracing the student's knowledge state during learning has been studied for several decades in order to provide more supportive learning instructions. In this paper, we propose a novel model for knowledge tracing that i) captures students' learning ability and dynamically assigns students into distinct groups with similar ability at regular time intervals, and ii) combines this information with a Recurrent Neural Network architecture known as Deep Knowledge Tracing. Experimental results confirm that the proposed model is significantly better at predicting student performance than well known state-of-the-art techniques for student modelling.
GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration
Venue: arXiv cs.LG 2021
Year: 2021

Despite advances in scalable models, the inference tools used for Gaussian processes (GPs) have yet to fully capitalize on developments in computing hardware. We present an efficient and general approach to GP inference based on Blackbox Matrix-Matrix multiplication (BBMM). BBMM inference uses a modified batched version of the conjugate gradients algorithm to derive all terms for training and inference in a single call. BBMM reduces the asymptotic complexity of exact GP inference from $O(n^3)$ to $O(n^2)$. Adapting this algorithm to scalable approximations and complex GP models simply requires a routine for efficient matrix-matrix multiplication with the kernel and its derivative. In addition, BBMM uses a specialized preconditioner to substantially speed up convergence. In experiments we show that BBMM effectively uses GPU hardware to dramatically accelerate both exact GP inference and scalable approximations. Additionally, we provide GPyTorch, a software platform for scalable GP inference via BBMM, built on PyTorch.
Temporal Cliques Admit Sparse Spanners
Venue: arXiv cs.DM 2021
Year: 2021

Let $G=(V,E)$ be an undirected graph on $n$ vertices and $λ:E\to 2^{\mathbb{N}}$ a mapping that assigns to every edge a non-empty set of integer labels (times). Such a graph is {\em temporally connected} if a path exists with non-decreasing times from every vertex to every other vertex. In a seminal paper, Kempe, Kleinberg, and Kumar \cite{KKK02} asked whether, given such a temporal graph, a {\em sparse} subset of edges always exists whose labels suffice to preserve temporal connectivity -- a {\em temporal spanner}. Axiotis and Fotakis \cite{AF16} answered negatively by exhibiting a family of $Θ(n^2)$-dense temporal graphs which admit no temporal spanner of density $o(n^2)$. In this paper, we give the first positive answer as to the existence of $o(n^2)$-sparse spanners in a dense class of temporal graphs, by showing (constructively) that if $G$ is a complete graph, then one can always find a temporal spanner of density $O(n \log n)$.
Recurrent Transition Networks for Character Locomotion
Venue: arXiv cs.GR 2021
Year: 2021

Manually authoring transition animations for a complete locomotion system can be a tedious and time-consuming task, especially for large games that allow complex and constrained locomotion movements, where the number of transitions grows exponentially with the number of states. In this paper, we present a novel approach, based on deep recurrent neural networks, to automatically generate such transitions given a past context of a few frames and a target character state to reach. We present the Recurrent Transition Network (RTN), based on a modified version of the Long-Short-Term-Memory (LSTM) network, designed specifically for transition generation and trained without any gait, phase, contact or action labels. We further propose a simple yet principled way to initialize the hidden states of the LSTM layer for a given sequence which improves the performance and generalization to new motions. We both quantitatively and qualitatively evaluate our system and show that making the network terrain-aware by adding a local terrain representation to the input yields better performance for rough-terrain navigation on long transitions. Our system produces realistic and fluid transitions that rival the quality of Motion Capture-based ground-truth motions, even before applying any inverse-kinematics postprocess. Direct benefits of our approach could be to accelerate the creation of transition variations for large coverage, or even to entirely replace transition nodes in an animation graph. We further explore applications of this model in a animation super-resolution setting where we temporally decompress animations saved at 1 frame per second and show that the network is able to reconstruct motions that are hard to distinguish from un-compressed locomotion sequences.
Learning to Optimize under Non-Stationarity
Venue: arXiv cs.LG 2021
Year: 2021

We introduce algorithms that achieve state-of-the-art \emph{dynamic regret} bounds for non-stationary linear stochastic bandit setting. It captures natural applications such as dynamic pricing and ads allocation in a changing environment. We show how the difficulty posed by the non-stationarity can be overcome by a novel marriage between stochastic and adversarial bandits learning algorithms. Defining $d,B_T,$ and $T$ as the problem dimension, the \emph{variation budget}, and the total time horizon, respectively, our main contributions are the tuned Sliding Window UCB (\texttt{SW-UCB}) algorithm with optimal $\widetilde{O}(d^{2/3}(B_T+1)^{1/3}T^{2/3})$ dynamic regret, and the tuning free bandit-over-bandit (\texttt{BOB}) framework built on top of the \texttt{SW-UCB} algorithm with best $\widetilde{O}(d^{2/3}(B_T+1)^{1/4}T^{3/4})$ dynamic regret.
First-order and second-order variants of the gradient descent in a unified framework
Venue: arXiv cs.LG 2021
Year: 2021

In this paper, we provide an overview of first-order and second-order variants of the gradient descent method that are commonly used in machine learning. We propose a general framework in which 6 of these variants can be interpreted as different instances of the same approach. They are the vanilla gradient descent, the classical and generalized Gauss-Newton methods, the natural gradient descent method, the gradient covariance matrix approach, and Newton's method. Besides interpreting these methods within a single framework, we explain their specificities and show under which conditions some of them coincide.