OpenRaiser/Intern-Atlas huggingface dataset:
Computing the Extremal Possible Ranks with Incomplete Preferences
Venue: arXiv cs.GT 2021
Year: 2021

Various voting rules are based on ranking the candidates by scores induced by aggregating voter preferences. A winner (respectively, unique winner) is a candidate who receives a score not smaller than (respectively, strictly greater than) the remaining candidates. Examples of such rules include the positional scoring rules and the Bucklin, Copeland, and Maximin rules. When voter preferences are known in an incomplete manner as partial orders, a candidate can be a possible/necessary winner based on the possibilities of completing the partial votes. Past research has studied in depth the computational problems of determining the possible and necessary winners and unique winners. These problems are all special cases of reasoning about the range of possible positions of a candidate under different tiebreakers. We investigate the complexity of determining this range, and particularly the extremal positions. Among our results, we establish that finding each of the minimal and maximal positions is NP-hard for each of the above rules, including all positional scoring rules, pure or not. Hence, none of the tractable variants of necessary/possible winner determination remain tractable for extremal position determination. Tractability can be retained when reasoning about the top-$k$ positions for a fixed $k$. Yet, exceptional is Maximin where it is tractable to decide whether the maximal rank is $k$ for $k=1$ (necessary winning) but it becomes intractable for all $k>1$.
Safe Learning for Near Optimal Scheduling
Venue: arXiv cs.AI 2021
Year: 2021

In this paper, we investigate the combination of synthesis, model-based learning, and online sampling techniques to obtain safe and near-optimal schedulers for a preemptible task scheduling problem. Our algorithms can handle Markov decision processes (MDPs) that have 1020 states and beyond which cannot be handled with state-of-the art probabilistic model-checkers. We provide probably approximately correct (PAC) guarantees for learning the model. Additionally, we extend Monte-Carlo tree search with advice, computed using safety games or obtained using the earliest-deadline-first scheduler, to safely explore the learned model online. Finally, we implemented and compared our algorithms empirically against shielded deep Q-learning on large task systems.
"Guess Who ?" Large-Scale Data-Centric Study of the Adequacy of Browser Fingerprints for Web Authentication
Venue: arXiv cs.CR 2021
Year: 2021

Browser fingerprinting consists in collecting attributes from a web browser to build a browser fingerprint. In this work, we assess the adequacy of browser fingerprints as an authentication factor, on a dataset of 4,145,408 fingerprints composed of 216 attributes. It was collected throughout 6 months from a population of general browsers. We identify, formalize, and assess the properties for browser fingerprints to be usable and practical as an authentication factor. We notably evaluate their distinctiveness, their stability through time, their collection time, and their size in memory. We show that considering a large surface of 216 fingerprinting attributes leads to an unicity rate of 81% on a population of 1,989,365 browsers. Moreover, browser fingerprints are known to evolve, but we observe that between consecutive fingerprints, more than 90% of the attributes remain unchanged after nearly 6 months. Fingerprints are also affordable. On average, they weigh a dozen of kilobytes, and are collected in a few seconds. We conclude that browser fingerprints are a promising additional web authentication factor.
Growth of bilinear maps
Venue: arXiv cs.DM 2021
Year: 2021

For a bilinear map $*:\mathbb R^d\times \mathbb R^d\to \mathbb R^d$ of nonnegative coefficients and a vector $s\in \mathbb R^d$ of positive entries, among an exponentially number of ways combining $n$ instances of $s$ using $n-1$ applications of $*$ for a given $n$, we are interested in the largest entry over all the resulting vectors. An asymptotic behavior is that the $n$-th root of this largest entry converges to a growth rate $λ$ when $n$ tends to infinity. In this paper, we prove the existence of this limit by a special structure called linear pattern. We also pose a question on the possibility of a relation between the structure and whether $λ$ is algebraic.
Throughput and Age of Information in a Cellular-based IoT Network
Venue: arXiv cs.IT 2021
Year: 2021

This paper studies the interplay between device-to-device (D2D) communications and real-time monitoring systems in a cellular-based Internet of Things (IoT) network. In particular, besides the possibility that the IoT devices communicate directly with each other in a D2D fashion, we consider that they frequently send time-sensitive information/status updates (about some underlying physical processes) to their nearest base stations (BSs). By modeling the locations of the IoT devices as a bipolar Poisson Point Process (PPP) and that of the BSs as another independent PPP, we characterize the performance of the D2D links and status update links in terms of network throughput and Age-of-Information (AoI), respectively. We consider a maximum power constraint and distance-dependent fractional power control for all status update transmissions. Hence, the locations of the IoT devices allowed to send status updates are constrained to lie within the Johnson-Mehl cells. For this set-up, the average network throughput is obtained by deriving the mean success probability of the D2D links, whereas the spatial moments of the temporal mean AoI are obtained by deriving the moments of the temporal means of both success and scheduling probabilities of the status update links.
Information-Theoretic Abstractions for Planning in Agents with Computational Constraints
Venue: arXiv cs.RO 2021
Year: 2021

In this paper, we develop a framework for path-planning on abstractions that are not provided to the agent a priori but instead emerge as a function of the available computational resources. We show how a path-planning problem in an environment can be systematically approximated by solving a sequence of easier to solve problems on abstractions of the original space. The properties of the problem are analyzed, and a number of theoretical results are presented and discussed. A numerical example is presented to show the utility of the approach and to corroborate the theoretical findings. We conclude by providing a discussion detailing the connections of the proposed approach to anytime algorithms and bounded rationality.
High Velocity Kernel File Systems with Bento
Venue: arXiv cs.OS 2021
Year: 2021

High development velocity is critical for modern systems. This is especially true for Linux file systems which are seeing increased pressure from new storage devices and new demands on storage systems. However, high velocity Linux kernel development is challenging due to the ease of introducing bugs, the difficulty of testing and debugging, and the lack of support for redeployment without service disruption. Existing approaches to high-velocity development of file systems for Linux have major downsides, such as the high performance penalty for FUSE file systems, slowing the deployment cycle for new file system functionality. We propose Bento, a framework for high velocity development of Linux kernel file systems. It enables file systems written in safe Rust to be installed in the Linux kernel, with errors largely sandboxed to the file system. Bento file systems can be replaced with no disruption to running applications, allowing daily or weekly upgrades in a cloud server setting. Bento also supports userspace debugging. We implement a simple file system using Bento and show that it performs similarly to VFS-native ext4 on a variety of benchmarks and outperforms a FUSE version by 7x on 'git clone'. We also show that we can dynamically add file provenance tracking to a running kernel file system with only 15ms of service interruption.
Context-Aware Learning to Rank with Self-Attention
Venue: arXiv cs.IR 2021
Year: 2021

Learning to rank is a key component of many e-commerce search engines. In learning to rank, one is interested in optimising the global ordering of a list of items according to their utility for users.Popular approaches learn a scoring function that scores items individually (i.e. without the context of other items in the list) by optimising a pointwise, pairwise or listwise loss. The list is then sorted in the descending order of the scores. Possible interactions between items present in the same list are taken into account in the training phase at the loss level. However, during inference, items are scored individually, and possible interactions between them are not considered. In this paper, we propose a context-aware neural network model that learns item scores by applying a self-attention mechanism. The relevance of a given item is thus determined in the context of all other items present in the list, both in training and in inference. We empirically demonstrate significant performance gains of self-attention based neural architecture over Multi-LayerPerceptron baselines, in particular on a dataset coming from search logs of a large scale e-commerce marketplace, Allegro.pl. This effect is consistent across popular pointwise, pairwise and listwise losses.Finally, we report new state-of-the-art results on MSLR-WEB30K, the learning to rank benchmark.
Representation of Developer Expertise in Open Source Software
Venue: arXiv cs.SE 2021
Year: 2021

Background: Accurate representation of developer expertise has always been an important research problem. While a number of studies proposed novel methods of representing expertise within individual projects, these methods are difficult to apply at an ecosystem level. However, with the focus of software development shifting from monolithic to modular, a method of representing developers' expertise in the context of the entire OSS development becomes necessary when, for example, a project tries to find new maintainers and look for developers with relevant skills. Aim: We aim to address this knowledge gap by proposing and constructing the Skill Space where each API, developer, and project is represented and postulate how the topology of this space should reflect what developers know (and projects need). Method: we use the World of Code infrastructure to extract the complete set of APIs in the files changed by open source developers and, based on that data, employ Doc2Vec embeddings for vector representations of APIs, developers, and projects. We then evaluate if these embeddings reflect the postulated topology of the Skill Space by predicting what new APIs/projects developers use/join, and whether or not their pull requests get accepted. We also check how the developers' representations in the Skill Space align with their self-reported API expertise. Result: Our results suggest that the proposed embeddings in the Skill Space appear to satisfy the postulated topology and we hope that such representations may aid in the construction of signals that increase trust (and efficiency) of open source ecosystems at large and may aid investigations of other phenomena related to developer proficiency and learning.
Sequential Universal Modeling for Non-Binary Sequences with Constrained Distributions
Venue: arXiv cs.IT 2021
Year: 2021

Sequential probability assignment and universal compression go hand in hand. We propose sequential probability assignment for non-binary (and large alphabet) sequences with empirical distributions whose parameters are known to be bounded within a limited interval. Sequential probability assignment algorithms are essential in many applications that require fast and accurate estimation of the maximizing sequence probability. These applications include learning, regression, channel estimation and decoding, prediction, and universal compression. On the other hand, constrained distributions introduce interesting theoretical twists that must be overcome in order to present efficient sequential algorithms. Here, we focus on universal compression for memoryless sources, and present precise analysis for the maximal minimax and the average minimax for constrained distributions. We show that our sequential algorithm based on modified Krichevsky-Trofimov (KT) estimator is asymptotically optimal up to $O(1)$ for both maximal and average redundancies. This paper follows and addresses the challenge presented in \cite{stw08} that suggested "results for the binary case lay the foundation to studying larger alphabets".
InfoScrub: Towards Attribute Privacy by Targeted Obfuscation
Venue: arXiv cs.CV 2021
Year: 2021

Personal photos of individuals when shared online, apart from exhibiting a myriad of memorable details, also reveals a wide range of private information and potentially entails privacy risks (e.g., online harassment, tracking). To mitigate such risks, it is crucial to study techniques that allow individuals to limit the private information leaked in visual data. We tackle this problem in a novel image obfuscation framework: to maximize entropy on inferences over targeted privacy attributes, while retaining image fidelity. We approach the problem based on an encoder-decoder style architecture, with two key novelties: (a) introducing a discriminator to perform bi-directional translation simultaneously from multiple unpaired domains; (b) predicting an image interpolation which maximizes uncertainty over a target set of attributes. We find our approach generates obfuscated images faithful to the original input images, and additionally increase uncertainty by 6.2$\times$ (or up to 0.85 bits) over the non-obfuscated counterparts.
Mapping Matters: Application Process Mapping on 3-D Processor Topologies
Venue: arXiv cs.DC 2021
Year: 2021

Applications' performance is influenced by the mapping of processes to computing nodes, the frequency and volume of exchanges among processing elements, the network capacity, and the routing protocol. A poor mapping of application processes degrades performance and wastes resources. Process mapping is frequently ignored as an explicit optimization step since the system typically offers a default mapping, users may lack awareness of their applications' communication behavior, and the opportunities for improving performance through mapping are often unclear. This work studies the impact of application process mapping on several processor topologies. We propose a workflow that renders mapping as an explicit optimization step for parallel applications. We apply the workflow to a set of four applications, twelve mapping algorithms, and three direct network topologies. We assess the mappings' quality in terms of volume, frequency, and distance of exchanges using metrics such as dilation (measured in hop$\cdot$Byte). With a parallel trace-based simulator, we predict the applications' execution on the three topologies using the twelve mappings. We evaluate the impact of process mapping on the applications' simulated performance in terms of execution and communication times and identify the mappings that achieve the highest performance in both cases. To ensure the correctness of the simulations, we compare the pre- and post-simulation results. This work emphasizes the importance of process mapping as an explicit optimization step and offers a solution for parallel applications to exploit the full potential of the allocated resources on a given system.
Global Multiclass Classification and Dataset Construction via Heterogeneous Local Experts
Venue: arXiv cs.LG 2021
Year: 2021

In the domains of dataset construction and crowdsourcing, a notable challenge is to aggregate labels from a heterogeneous set of labelers, each of whom is potentially an expert in some subset of tasks (and less reliable in others). To reduce costs of hiring human labelers or training automated labeling systems, it is of interest to minimize the number of labelers while ensuring the reliability of the resulting dataset. We model this as the problem of performing $K$-class classification using the predictions of smaller classifiers, each trained on a subset of $[K]$, and derive bounds on the number of classifiers needed to accurately infer the true class of an unlabeled sample under both adversarial and stochastic assumptions. By exploiting a connection to the classical set cover problem, we produce a near-optimal scheme for designing such configurations of classifiers which recovers the well known one-vs.-one classification approach as a special case. Experiments with the MNIST and CIFAR-10 datasets demonstrate the favorable accuracy (compared to a centralized classifier) of our aggregation scheme applied to classifiers trained on subsets of the data. These results suggest a new way to automatically label data or adapt an existing set of local classifiers to larger-scale multiclass problems.
Automatic Detection of Influential Actors in Disinformation Networks
Venue: arXiv cs.SI 2021
Year: 2021

The weaponization of digital communications and social media to conduct disinformation campaigns at immense scale, speed, and reach presents new challenges to identify and counter hostile influence operations (IOs). This paper presents an end-to-end framework to automate detection of disinformation narratives, networks, and influential actors. The framework integrates natural language processing, machine learning, graph analytics, and a novel network causal inference approach to quantify the impact of individual actors in spreading IO narratives. We demonstrate its capability on real-world hostile IO campaigns with Twitter datasets collected during the 2017 French presidential elections, and known IO accounts disclosed by Twitter over a broad range of IO campaigns (May 2007 to February 2020), over 50,000 accounts, 17 countries, and different account types including both trolls and bots. Our system detects IO accounts with 96% precision, 79% recall, and 96% area-under-the-PR-curve, maps out salient network communities, and discovers high-impact accounts that escape the lens of traditional impact statistics based on activity counts and network centrality. Results are corroborated with independent sources of known IO accounts from U.S. Congressional reports, investigative journalism, and IO datasets provided by Twitter.
Symbolic Reasoning about Quantum Circuits in Coq
Venue: arXiv cs.PL 2021
Year: 2021

A quantum circuit is a computational unit that transforms an input quantum state to an output one. A natural way to reason about its behavior is to compute explicitly the unitary matrix implemented by it. However, when the number of qubits increases, the matrix dimension grows exponentially and the computation becomes intractable. In this paper, we propose a symbolic approach to reasoning about quantum circuits. It is based on a small set of laws involving some basic manipulations on vectors and matrices. This symbolic reasoning scales better than the explicit one and is well suited to be automated in Coq, as demonstrated with some typical examples.
VDO-SLAM: A Visual Dynamic Object-aware SLAM System
Venue: arXiv cs.RO 2021
Year: 2021

Combining Simultaneous Localisation and Mapping (SLAM) estimation and dynamic scene modelling can highly benefit robot autonomy in dynamic environments. Robot path planning and obstacle avoidance tasks rely on accurate estimations of the motion of dynamic objects in the scene. This paper presents VDO-SLAM, a robust visual dynamic object-aware SLAM system that exploits semantic information to enable accurate motion estimation and tracking of dynamic rigid objects in the scene without any prior knowledge of the objects' shape or geometric models. The proposed approach identifies and tracks the dynamic objects and the static structure in the environment and integrates this information into a unified SLAM framework. This results in highly accurate estimates of the robot's trajectory and the full SE(3) motion of the objects as well as a spatiotemporal map of the environment. The system is able to extract linear velocity estimates from objects' SE(3) motion providing an important functionality for navigation in complex dynamic environments. We demonstrate the performance of the proposed system on a number of real indoor and outdoor datasets and the results show consistent and substantial improvements over the state-of-the-art algorithms. An open-source version of the source code is available.
Towards a Neural Model for Serial Order in Frontal Cortex: a Brain Theory from Memory Development to Higher-Level Cognition
Venue: arXiv cs.NE 2021
Year: 2021

In order to keep trace of information and grow up, the infant brain has to resolve the problem about where old information is located and how to index new ones. We propose that the immature prefrontal cortex (PFC) use its primary functionality of detecting hierarchical patterns in temporal signals as a second purpose to organize the spatial ordering of the cortical networks in the developing brain itself. Our hypothesis is that the PFC detects the hierarchical structure in temporal sequences in the form of ordinal patterns and use them to index information hierarchically in different parts of the brain. Henceforth, we propose that this mechanism for detecting patterns participates in the ordinal organization development of the brain itself; i.e., the bootstrapping of the connectome. By doing so, it gives the tools to the language-ready brain for manipulating abstract knowledge and planning temporally ordered information; i.e., the emergence of symbolic thinking and language. We will review neural models that can support such mechanisms and propose new ones. We will confront then our ideas with evidence from developmental, behavioral and brain results and make some hypotheses, for instance, on the construction of the mirror neuron system, on embodied cognition, and on the capacity of learning-to-learn.
Spectrally-Encoded Single-Pixel Machine Vision Using Diffractive Networks
Venue: arXiv cs.CV 2021
Year: 2021

3D engineering of matter has opened up new avenues for designing systems that can perform various computational tasks through light-matter interaction. Here, we demonstrate the design of optical networks in the form of multiple diffractive layers that are trained using deep learning to transform and encode the spatial information of objects into the power spectrum of the diffracted light, which are used to perform optical classification of objects with a single-pixel spectroscopic detector. Using a time-domain spectroscopy setup with a plasmonic nanoantenna-based detector, we experimentally validated this machine vision framework at terahertz spectrum to optically classify the images of handwritten digits by detecting the spectral power of the diffracted light at ten distinct wavelengths, each representing one class/digit. We also report the coupling of this spectral encoding achieved through a diffractive optical network with a shallow electronic neural network, separately trained to reconstruct the images of handwritten digits based on solely the spectral information encoded in these ten distinct wavelengths within the diffracted light. These reconstructed images demonstrate task-specific image decompression and can also be cycled back as new inputs to the same diffractive network to improve its optical object classification. This unique machine vision framework merges the power of deep learning with the spatial and spectral processing capabilities of diffractive networks, and can also be extended to other spectral-domain measurement systems to enable new 3D imaging and sensing modalities integrated with spectrally encoded classification tasks performed through diffractive optical networks.