OpenRaiser/Intern-Atlas huggingface dataset:
Minimizing convex quadratic with variable precision conjugate gradients
Venue: arXiv cs.NA 2020
Year: 2020

We investigate the method of conjugate gradients, exploiting inaccurate matrix-vector products, for the solution of convex quadratic optimization problems. Theoretical performance bounds are derived, and the necessary quantities occurring in the theoretical bounds estimated, leading to a practical algorithm. Numerical experiments suggest that this approach has significant potential, including in the steadily more important context of multi-precision computations
Enhanced adaptive surrogate models with applications in uncertainty quantification for nanoplasmonics
Venue: arXiv cs.CE 2020
Year: 2020

We propose an efficient surrogate modeling technique for uncertainty quantification. The method is based on a well-known dimension-adaptive collocation scheme. We improve the scheme by enhancing sparse polynomial surrogates with conformal maps and adjoint error correction. The methodology is applied to Maxwell's source problem with random input data. This setting comprises many applications of current interest from computational nanoplasmonics, such as grating couplers or optical waveguides. Using a non-trivial benchmark model we show the benefits and drawbacks of using enhanced surrogate models through various numerical studies. The proposed strategy allows us to conduct a thorough uncertainty analysis, taking into account a moderately large number of random parameters.
Blind Signal Classification for Non-Orthogonal Multiple Access in Vehicular Networks
Venue: arXiv cs.IT 2020
Year: 2020

For downlink multiple-user (MU) transmission based on non-orthogonal multiple access (NOMA), the advanced receiver strategy is required to cancel the inter-user interference, e.g., successive interference cancellation (SIC). The SIC process can be applicable only when information about the co-scheduled signal is known at the user terminal (UT) side. In particular, the UT should know whether the received signal is OMA or NOMA, whether SIC is required or not, and which modulation orders and power ratios have been used for the superposed UTs, before decoding the signal. An efficient network, e.g., vehicular network, requires that the UTs blindly classify the received signal and apply a matching receiver strategy to reduce the high-layer signaling overhead which is essential for high-mobility vehicular networks. In this paper, we first analyze the performance impact of errors in NOMA signal classification and address ensuing receiver challenges in practical MU usage cases. In order to reduce the blind signal classification error rate, we propose transmission schemes that rotate data symbols or pilots to a specific phase according to the transmitted signal format. In the case of pilot rotation, a new signal classification algorithm is also proposed. The performance improvements by the proposed methods are verified by intensive simulation results.
Undecidability of a weak version of MSO+U
Venue: arXiv cs.LO 2020
Year: 2020

We prove the undecidability of MSO on $ω$-words extended with the second-order predicate $U_1(X)$ which says that the distance between consecutive positions in a set $X \subseteq \mathbb{N}$ is unbounded. This is achieved by showing that adding $U_1$ to MSO gives a logic with the same expressive power as $MSO+U$, a logic on $ω$-words with undecidable satisfiability. As a corollary, we prove that MSO on $ω$-words becomes undecidable if allowing to quantify over sets of positions that are ultimately periodic, i.e., sets $X$ such that for some positive integer $p$, ultimately either both or none of positions $x$ and $x+p$ belong to $X$.
Particle Filtering Methods for Stochastic Optimization with Application to Large-Scale Empirical Risk Minimization
Venue: arXiv cs.LG 2020
Year: 2020

This paper is concerned with sequential filtering based stochastic optimization (FSO) approaches that leverage a probabilistic perspective to implement the incremental proximity method (IPM). The present FSO methods are derived based on the Kalman filter (KF) and the extended KF (EKF). In contrast with typical methods such as stochastic gradient descent (SGD) and IPMs, they do not need to pre-schedule the learning rate for convergence. Nevertheless, they have limitations that inherit from the KF mechanism. As the particle filtering (PF) method outperforms KF and its variants remarkably for nonlinear non-Gaussian sequential filtering problems, it is natural to ask if FSO methods can benefit from PF to get around of their limitations. We provide an affirmative answer to this question by developing two PF based stochastic optimizers (PFSOs). For performance evaluation, we apply them to address nonlinear least-square fitting with simulated data, and empirical risk minimization for binary classification of real data sets. Experimental results demonstrate that PFSOs outperform remarkably a benchmark SGD algorithm, the vanilla IPM, and KF-type FSO methods in terms of numerical stability, convergence speed, and flexibility in handling diverse types of loss functions.
The division of labor in communication: Speakers help listeners account for asymmetries in visual perspective
Venue: arXiv cs.CL 2020
Year: 2020

Recent debates over adults' theory of mind use have been fueled by surprising failures of perspective-taking in communication, suggesting that perspective-taking can be relatively effortful. How, then, should speakers and listeners allocate their resources to achieve successful communication? We begin with the observation that this shared goal induces a natural division of labor: the resources one agent chooses to allocate toward perspective-taking should depend on their expectations about the other's allocation. We formalize this idea in a resource-rational model augmenting recent probabilistic weighting accounts with a mechanism for (costly) control over the degree of perspective-taking. In a series of simulations, we first derive an intermediate degree of perspective weighting as an optimal tradeoff between expected costs and benefits of perspective-taking. We then present two behavioral experiments testing novel predictions of our model. In Experiment 1, we manipulated the presence or absence of occlusions in a director-matcher task and found that speakers spontaneously produced more informative descriptions to account for "known unknowns" in their partner's private view. In Experiment 2, we compared the scripted utterances used by confederates in prior work with those produced in interactions with unscripted directors. We found that confederates were systematically less informative than listeners would initially expect given the presence of occlusions, but listeners used violations to adaptively make fewer errors over time. Taken together, our work suggests that people are not simply "mindblind"; they use contextually appropriate expectations to navigate the division of labor with their partner. We discuss how a resource rational framework may provide a more deeply explanatory foundation for understanding flexible perspective-taking under processing constraints.
Constant-Delay Enumeration for Nondeterministic Document Spanners
Venue: arXiv cs.DB 2020
Year: 2020

We consider the information extraction framework known as document spanners, and study the problem of efficiently computing the results of the extraction from an input document, where the extraction task is described as a sequential variable-set automaton (VA). We pose this problem in the setting of enumeration algorithms, where we can first run a preprocessing phase and must then produce the results with a small delay between any two consecutive results. Our goal is to have an algorithm which is tractable in combined complexity, i.e., in the sizes of the input document and the VA; while ensuring the best possible data complexity bounds in the input document size, i.e., constant delay in the document size. Several recent works at PODS'18 proposed such algorithms but with linear delay in the document size or with an exponential dependency in size of the (generally nondeterministic) input VA. In particular, Florenzano et al. suggest that our desired runtime guarantees cannot be met for general sequential VAs. We refute this and show that, given a nondeterministic sequential VA and an input document, we can enumerate the mappings of the VA on the document with the following bounds: the preprocessing is linear in the document size and polynomial in the size of the VA, and the delay is independent of the document and polynomial in the size of the VA. The resulting algorithm thus achieves tractability in combined complexity and the best possible data complexity bounds. Moreover, it is rather easy to describe, in particular for the restricted case of so-called extended VAs.
Contrastive Video Representation Learning via Adversarial Perturbations
Venue: arXiv cs.CV 2020
Year: 2020

Adversarial perturbations are noise-like patterns that can subtly change the data, while failing an otherwise accurate classifier. In this paper, we propose to use such perturbations within a novel contrastive learning setup to build negative samples, which are then used to produce improved video representations. To this end, given a well-trained deep model for per-frame video recognition, we first generate adversarial noise adapted to this model. Positive and negative bags are produced using the original data features from the full video sequence and their perturbed counterparts, respectively. Unlike the classic contrastive learning methods, we develop a binary classification problem that learns a set of discriminative hyperplanes -- as a subspace -- that will separate the two bags from each other. This subspace is then used as a descriptor for the video, dubbed \emph{discriminative subspace pooling}. As the perturbed features belong to data classes that are likely to be confused with the original features, the discriminative subspace will characterize parts of the feature space that are more representative of the original data, and thus may provide robust video representations. To learn such descriptors, we formulate a subspace learning objective on the Stiefel manifold and resort to Riemannian optimization methods for solving it efficiently. We provide experiments on several video datasets and demonstrate state-of-the-art results.
NMT-based Cross-lingual Document Embeddings
Venue: arXiv cs.CL 2020
Year: 2020

This paper investigates a cross-lingual document embedding method that improves the current Neural machine Translation framework based Document Vector (NTDV or simply NV). NV is developed with a self-attention mechanism under the neural machine translation (NMT) framework. In NV, each pair of parallel documents in different languages are projected to the same shared layer in the model. However, the pair of NV embeddings are not guaranteed to be similar. This paper further adds a distance constraint to the training objective function of NV so that the two embeddings of a parallel document are required to be as close as possible. The new method will be called constrained NV (cNV). In a cross-lingual document classification task, the new cNV performs as well as NV and outperforms other published studies that require forward-pass decoding. Compared with the previous NV, cNV does not need a translator during testing, and so the method is lighter and more flexible.
Robust Distributed Planar Formation Control for Higher-Order Holonomic and Nonholonomic Agents
Venue: arXiv cs.RO 2020
Year: 2020

We present a distributed formation control strategy for agents with a variety of dynamics to achieve a desired planar formation. Our approach is based on the barycentric-coordinate-based (BCB) control, which is fully distributed, does not require inter-agent communication or a common sense of orientation, and can be implemented using relative position measurements acquired by agents in their local coordinate frames. This removes the need for global positioning or alignment of local coordinate frames, which are required across several existing strategies. We show how the BCB control for agents with the simplest dynamical model, i.e., the single-integrator dynamics, can be extended to agents with higher-order dynamics such as quadrotors, and nonholonomic agents such as unicycles and cars. Specifically, our extension preserves the desired convergence and robustness guarantees of the BCB approach and is provably robust to saturations in the input and unmodeled linear actuator dynamics for unicycle and car agents. We further show that under our proposed BCB control design, the agents can move along a rotated and scaled control direction without affecting the convergence to the desired formation. This observation is used to design a fully distributed collision avoidance strategy, which is often not considered in the formation control literature. We demonstrate the proposed approach in simulations and further present a distributed robotic platform to test the strategy experimentally. Our experimental platform consists of off-the-shelf equipment that can be used to test and validate other multi-agent algorithms. The code and implementation instructions for this platform are available online.
HARMONIC: A Multimodal Dataset of Assistive Human-Robot Collaboration
Venue: arXiv cs.RO 2020
Year: 2020

We present the Human And Robot Multimodal Observations of Natural Interactive Collaboration (HARMONIC) data set. This is a large multimodal data set of human interactions with a robotic arm in a shared autonomy setting designed to imitate assistive eating. The data set provides human, robot, and environmental data views of twenty-four different people engaged in an assistive eating task with a 6 degree-of-freedom (DOF) robot arm. From each participant, we recorded video of both eyes, egocentric video from a head-mounted camera, joystick commands, electromyography from the forearm used to operate the joystick, third person stereo video, and the joint positions of the 6 DOF robot arm. Also included are several features that come as a direct result of these recordings, such as eye gaze projected onto the egocentric video, body pose, hand pose, and facial keypoints. These data streams were collected specifically because they have been shown to be closely related to human mental states and intention. This data set could be of interest to researchers studying intention prediction, human mental state modeling, and shared autonomy. Data streams are provided in a variety of formats such as video and human-readable CSV and YAML files.
Norms, Institutions, and Robots
Venue: arXiv cs.AI 2020
Year: 2020

Interactions within human societies are usually regulated by social norms. If robots are to be accepted into human society, it is essential that they are aware of and capable of reasoning about social norms. In this paper, we focus on how to represent social norms in societies with humans and robots, and how artificial agents such as robots can reason about social norms in order to plan appropriate behavior. We use the notion of institution as a way to formally define and encapsulate norms, and we provide a formal framework for institutions. Our framework borrows ideas from the field of multi-agent systems to define abstract normative models, and ideas from the field of robotics to define physical executions as state-space trajectories. By bridging the two in a common model, our framework allows us to use the same abstract institution across physical domains and agent types. We then make our framework computational via a reduction to CSP and show experiments where this reduction is used for norm verification, planning, and plan execution in a domain including a mixture of humans and robots.
Reassembling the English novel, 1789-1919
Venue: arXiv cs.DL 2020
Year: 2020

The absence of an exhaustive bibliography of novels published in the British Isles and Ireland during the 19th century blocks several lines of research in sociologically-inclined literary history and book history. Without a detailed account of novelistic production, it is difficult to characterize, for example, the population of individuals who pursued careers as novelists. This paper contributes to efforts to develop such an account by estimating yearly rates of new novel publication in the British Isles and Ireland between 1789 and 1919. This period witnessed, in aggregate, the publication of between 40,000 and 63,000 previously unpublished novels. The number of new novels published each year counts as essential information for researchers interested in understanding the development of the text industry between 1789 and 1919.
Physics-Based Generative Adversarial Models for Image Restoration and Beyond
Venue: arXiv cs.CV 2020
Year: 2020

We present an algorithm to directly solve numerous image restoration problems (e.g., image deblurring, image dehazing, image deraining, etc.). These problems are highly ill-posed, and the common assumptions for existing methods are usually based on heuristic image priors. In this paper, we find that these problems can be solved by generative models with adversarial learning. However, the basic formulation of generative adversarial networks (GANs) does not generate realistic images, and some structures of the estimated images are usually not preserved well. Motivated by an interesting observation that the estimated results should be consistent with the observed inputs under the physics models, we propose a physics model constrained learning algorithm so that it can guide the estimation of the specific task in the conventional GAN framework. The proposed algorithm is trained in an end-to-end fashion and can be applied to a variety of image restoration and related low-level vision problems. Extensive experiments demonstrate that our method performs favorably against the state-of-the-art algorithms.
Histogram Transform-based Speaker Identification
Venue: arXiv cs.SD 2020
Year: 2020

A novel text-independent speaker identification (SI) method is proposed. This method uses the Mel-frequency Cepstral coefficients (MFCCs) and the dynamic information among adjacent frames as feature sets to capture speaker's characteristics. In order to utilize dynamic information, we design super-MFCCs features by cascading three neighboring MFCCs frames together. The probability density function (PDF) of these super-MFCCs features is estimated by the recently proposed histogram transform~(HT) method, which generates more training data by random transforms to realize the histogram PDF estimation and recedes the commonly occurred discontinuity problem in multivariate histograms computing. Compared to the conventional PDF estimation methods, such as Gaussian mixture models, the HT model shows promising improvement in the SI performance.
Peek-a-Boo: I see your smart home activities, even encrypted!
Venue: arXiv cs.CR 2020
Year: 2020

A myriad of IoT devices such as bulbs, switches, speakers in a smart home environment allow users to easily control the physical world around them and facilitate their living styles through the sensors already embedded in these devices. Sensor data contains a lot of sensitive information about the user and devices. However, an attacker inside or near a smart home environment can potentially exploit the innate wireless medium used by these devices to exfiltrate sensitive information from the encrypted payload (i.e., sensor data) about the users and their activities, invading user privacy. With this in mind,in this work, we introduce a novel multi-stage privacy attack against user privacy in a smart environment. It is realized utilizing state-of-the-art machine-learning approaches for detecting and identifying the types of IoT devices, their states, and ongoing user activities in a cascading style by only passively sniffing the network traffic from smart home devices and sensors. The attack effectively works on both encrypted and unencrypted communications. We evaluate the efficiency of the attack with real measurements from an extensive set of popular off-the-shelf smart home IoT devices utilizing a set of diverse network protocols like WiFi, ZigBee, and BLE. Our results show that an adversary passively sniffing the traffic can achieve very high accuracy (above 90%) in identifying the state and actions of targeted smart home devices and their users. To protect against this privacy leakage, we also propose a countermeasure based on generating spoofed traffic to hide the device states and demonstrate that it provides better protection than existing solutions.
Classifier-Guided Visual Correction of Noisy Labels for Image Classification Tasks
Venue: arXiv cs.CV 2020
Year: 2020

Training data plays an essential role in modern applications of machine learning. However, gathering labeled training data is time-consuming. Therefore, labeling is often outsourced to less experienced users, or completely automated. This can introduce errors, which compromise valuable training data, and lead to suboptimal training results. We thus propose a novel approach that uses the power of pretrained classifiers to visually guide users to noisy labels, and let them interactively check error candidates, to iteratively improve the training data set. To systematically investigate training data, we propose a categorization of labeling errors into three different types, based on an analysis of potential pitfalls in label acquisition processes. For each of these types, we present approaches to detect, reason about, and resolve error candidates, as we propose measures and visual guidance techniques to support machine learning users. Our approach has been used to spot errors in well-known machine learning benchmark data sets, and we tested its usability during a user evaluation. While initially developed for images, the techniques presented in this paper are independent of the classification algorithm, and can also be extended to many other types of training data.
Regular Tree Algebras
Venue: arXiv cs.FL 2020
Year: 2020

We introduce a class of algebras that can be used as recognisers for regular tree languages. We show that it is the only such class that forms a pseudo-variety and we prove the existence of syntactic algebras. Finally, we give a more algebraic characterisation of the algebras in our class.
How Complex is your classification problem? A survey on measuring classification complexity
Venue: arXiv cs.LG 2020
Year: 2020

Characteristics extracted from the training datasets of classification problems have proven to be effective predictors in a number of meta-analyses. Among them, measures of classification complexity can be used to estimate the difficulty in separating the data points into their expected classes. Descriptors of the spatial distribution of the data and estimates of the shape and size of the decision boundary are among the known measures for this characterization. This information can support the formulation of new data-driven pre-processing and pattern recognition techniques, which can in turn be focused on challenges highlighted by such characteristics of the problems. This paper surveys and analyzes measures which can be extracted from the training datasets in order to characterize the complexity of the respective classification problems. Their use in recent literature is also reviewed and discussed, allowing to prospect opportunities for future work in the area. Finally, descriptions are given on an R package named Extended Complexity Library (ECoL) that implements a set of complexity measures and is made publicly available.