OpenRaiser/Intern-Atlas huggingface dataset:
Semantically Grounded Object Matching for Robust Robotic Scene Rearrangement
Venue: arXiv cs.RO 2021
Year: 2021

Object rearrangement has recently emerged as a key competency in robot manipulation, with practical solutions generally involving object detection, recognition, grasping and high-level planning. Goal-images describing a desired scene configuration are a promising and increasingly used mode of instruction. A key outstanding challenge is the accurate inference of matches between objects in front of a robot, and those seen in a provided goal image, where recent works have struggled in the absence of object-specific training data. In this work, we explore the deterioration of existing methods' ability to infer matches between objects as the visual shift between observed and goal scenes increases. We find that a fundamental limitation of the current setting is that source and target images must contain the same $\textit{instance}$ of every object, which restricts practical deployment. We present a novel approach to object matching that uses a large pre-trained vision-language model to match objects in a cross-instance setting by leveraging semantics together with visual features as a more robust, and much more general, measure of similarity. We demonstrate that this provides considerably improved matching performance in cross-instance settings, and can be used to guide multi-object rearrangement with a robot manipulator from an image that shares no object $\textit{instances}$ with the robot's scene.
Towards Capturing PTIME with no Counting Construct (but with a Choice Operator)
Venue: arXiv cs.LO 2021
Year: 2021

The central open question in Descriptive Complexity is whether there is a logic that characterizes deterministic polynomial time (PTIME) on relational structures. Towards this goal, we define a logic that is obtained from first-order logic with fixed points, FO(FP), by a series of transformations that include restricting logical connectives and adding a dynamic version of Hilbert's Choice operator Epsilon. The formalism can be viewed, simultaneously, as an algebra of binary relations and as a linear-time modal dynamic logic, where algebraic expressions describing ``proofs'' or ``programs'' appear inside the modalities. We show how counting, reachability and ``mixed'' examples (that include linear equations modulo two) are axiomatized in the logic, and how an arbitrary PTIME Turing machine can be encoded. For each fixed Choice function, the data complexity of model checking is in PTIME. However, there can be exponentially many such functions. A crucial question is under what syntactic conditions on algebraic terms checking just one Choice function is sufficient. Answering this question requires a study of symmetries among computations. This paper sets mathematical foundations towards such a study via algebraic and automata-theoretic techniques.
Bag of Tricks and A Strong baseline for Image Copy Detection
Venue: arXiv cs.CV 2021
Year: 2021

Image copy detection is of great importance in real-life social media. In this paper, a bag of tricks and a strong baseline are proposed for image copy detection. Unsupervised pre-training substitutes the commonly-used supervised one. Beyond that, we design a descriptor stretching strategy to stabilize the scores of different queries. Experiments demonstrate that the proposed method is effective. The proposed baseline ranks third out of 526 participants on the Facebook AI Image Similarity Challenge: Descriptor Track. The code and trained models are available at https://github.com/WangWenhao0716/ISC-Track2-Submission.
Piano Fingering with Reinforcement Learning
Venue: arXiv cs.OH 2021
Year: 2021

Hand and finger movements are a mainstay of piano technique. Automatic Fingering from symbolic music data allows us to simulate finger and hand movements. Previous proposals achieve automatic piano fingering based on knowledge-driven or data-driven techniques. We combine both approaches with deep reinforcement learning techniques to derive piano fingering. Finally, we explore how to incorporate past experience into reinforcement learning-based piano fingering in further work.
A Multi-criteria Approach to Evolve Sparse Neural Architectures for Stock Market Forecasting
Venue: arXiv cs.NE 2021
Year: 2021

This study proposes a new framework to evolve efficacious yet parsimonious neural architectures for the movement prediction of stock market indices using technical indicators as inputs. In the light of a sparse signal-to-noise ratio under the Efficient Market hypothesis, developing machine learning methods to predict the movement of a financial market using technical indicators has shown to be a challenging problem. To this end, the neural architecture search is posed as a multi-criteria optimization problem to balance the efficacy with the complexity of architectures. In addition, the implications of different dominant trading tendencies which may be present in the pre-COVID and within-COVID time periods are investigated. An $ε-$ constraint framework is proposed as a remedy to extract any concordant information underlying the possibly conflicting pre-COVID data. Further, a new search paradigm, Two-Dimensional Swarms (2DS) is proposed for the multi-criteria neural architecture search, which explicitly integrates sparsity as an additional search dimension in particle swarms. A detailed comparative evaluation of the proposed approach is carried out by considering genetic algorithm and several combinations of empirical neural design rules with a filter-based feature selection method (mRMR) as baseline approaches. The results of this study convincingly demonstrate that the proposed approach can evolve parsimonious networks with better generalization capabilities.
Virtual Reality for Synergistic Surgical Training and Data Generation
Venue: arXiv cs.RO 2021
Year: 2021

Surgical simulators not only allow planning and training of complex procedures, but also offer the ability to generate structured data for algorithm development, which may be applied in image-guided computer assisted interventions. While there have been efforts on either developing training platforms for surgeons or data generation engines, these two features, to our knowledge, have not been offered together. We present our developments of a cost-effective and synergistic framework, named Asynchronous Multibody Framework Plus (AMBF+), which generates data for downstream algorithm development simultaneously with users practicing their surgical skills. AMBF+ offers stereoscopic display on a virtual reality (VR) device and haptic feedback for immersive surgical simulation. It can also generate diverse data such as object poses and segmentation maps. AMBF+ is designed with a flexible plugin setup which allows for unobtrusive extension for simulation of different surgical procedures. We show one use case of AMBF+ as a virtual drilling simulator for lateral skull-base surgery, where users can actively modify the patient anatomy using a virtual surgical drill. We further demonstrate how the data generated can be used for validating and training downstream computer vision algorithms
Moebius: Metaprogramming using Contextual Types -- The stage where System F can pattern match on itself (Long Version)
Venue: arXiv cs.PL 2021
Year: 2021

We describe the foundation of the metaprogramming language, Moebius, which supports the generation of polymorphic code and, more importantly the analysis of polymorphic code via pattern matching. Moebius has two main ingredients: 1) we exploit contextual modal types to describe open code together with the context in which it is meaningful. In Moebius, open code can depend on type and term variables (level 0) whose values are supplied at a later stage, as well as code variables (level 1) that stand for code templates supplied at a later stage. This leads to a multi-level modal lambda-calculus that supports System-F style polymorphism and forms the basis for polymorphic code generation. 2) we extend the multi-level modal lambda-calculus to support pattern matching on code. As pattern matching on polymorphic code may refine polymorphic type variables, we extend our type-theoretic foundation to generate and track typing constraints that arise. We also give an operational semantics and prove type preservation. Our multi-level modal foundation for Moebius provides the appropriate abstractions for both generating and pattern matching on open code without committing to a concrete representation of variable binding and contexts. Hence, our work is a step towards building a general type-theoretic foundation for multi-staged metaprogramming that, on the one hand, enforces strong type guarantees and, on the other hand, makes it easy to generate and manipulate code. This will allow us to exploit the full potential of metaprogramming without sacrificing the reliability of and trust in the code we are producing and running.
El impacto del buffer en la calidad de servicio
Venue: arXiv cs.NI 2021
Year: 2021

The response in data flows transmission in real time is analyzed, for access network scenarios, in which said flows converge on an outgoing link, competing to achieve a certain level of quality of service. The concurrence of these types of flows can generate bursts of packets, which in certain circumstances can compromise the capacity of the buffers to absorb packets in congestion periods. In addition, an analysis of the characteristics of buffers in access devices is presented, especially their size and packet loss. In particular, it describes how these characteristics can affect the quality of multimedia applications when bursty traffic is generated, it also presents possible effects on the traffic of other applications that share a common link.
Joint Unsupervised and Supervised Training for Multilingual ASR
Venue: arXiv cs.CL 2021
Year: 2021

Self-supervised training has shown promising gains in pretraining models and facilitating the downstream finetuning for speech recognition, like multilingual ASR. Most existing methods adopt a 2-stage scheme where the self-supervised loss is optimized in the first pretraining stage, and the standard supervised finetuning resumes in the second stage. In this paper, we propose an end-to-end (E2E) Joint Unsupervised and Supervised Training (JUST) method to combine the supervised RNN-T loss and the self-supervised contrastive and masked language modeling (MLM) losses. We validate its performance on the public dataset Multilingual LibriSpeech (MLS), which includes 8 languages and is extremely imbalanced. On MLS, we explore (1) JUST trained from scratch, and (2) JUST finetuned from a pretrained checkpoint. Experiments show that JUST can consistently outperform other existing state-of-the-art methods, and beat the monolingual baseline by a significant margin, demonstrating JUST's capability of handling low-resource languages in multilingual ASR. Our average WER of all languages outperforms average monolingual baseline by 33.3%, and the state-of-the-art 2-stage XLSR by 32%. On low-resource languages like Polish, our WER is less than half of the monolingual baseline and even beats the supervised transfer learning method which uses external supervision.
Improved Approximations for CVRP with Unsplittable Demands
Venue: arXiv cs.DS 2021
Year: 2021

In this paper, we present improved approximation algorithms for the (unsplittable) Capacitated Vehicle Routing Problem (CVRP) in general metrics. In CVRP, introduced by Dantzig and Ramser (1959), we are given a set of points (clients) $V$ together with a depot $r$ in a metric space, with each $v\in V$ having a demand $d_v>0$, and a vehicle of bounded capacity $Q$. The goal is to find a minimum cost collection of tours for the vehicle, each starting and ending at the depot, such that each client is visited at least once and the total demands of the clients in each tour is at most $Q$. In the unsplittable variant we study, the demand of a node must be served entirely by one tour. We present two approximation algorithms for unsplittable CVRP: a combinatorial $(α+1.75)$-approximation, where $α$ is the approximation factor for the Traveling Salesman Problem, and an approximation algorithm based on LP rounding with approximation guarantee $α+\ln(2) + δ\approx 3.194 + δ$ in $n^{O(1/δ)}$ time. Both approximations can further be improved by a small amount when combined with recent work by Blauth, Traub, and Vygen (2021), who obtained an $(α+ 2\cdot (1 -ε))$-approximation for unsplittable CVRP for some constant $ε$ depending on $α$ ($ε> 1/3000$ for $α= 1.5$).
Rearranging the Environment to Maximize Energy with a Robotic Circuit Drawing
Venue: arXiv cs.RO 2021
Year: 2021

Robots with the ability to actively acquire power from surroundings will be greatly beneficial for long-term autonomy and to survive in uncertain environments. In this work, we present a robot capable of drawing circuits with conductive ink while also rearranging the visual world to receive maximum energy from a power source. A range of circuit drawing tasks is designed to simulate real-world scenarios, including avoiding physical obstacles and regions that would discontinue drawn circuits. We adopt the state-of-the-art Transporter networks for pick-and-place manipulation from visual observation. We conduct experiments in both simulation and real-world settings, and our results show that, with a small number of demonstrations, the robot learns to rearrange the placement of objects (removing obstacles and bridging areas unsuitable for drawing) and to connect a power source with a minimum amount of conductive ink. As autonomous robots become more present, in our houses and other planets, our proposed method brings a novel way for machines to keep themselves functional by rearranging their surroundings to create their own electric circuits.
Is CADP an Applicable Formal Method?
Venue: arXiv cs.SE 2021
Year: 2021

CADP is a comprehensive toolbox implementing results of concurrency theory. This paper addresses the question, whether CADP qualifies as an applicable formal method, based on the experience of the authors and feedback reported by users.
NatiDroid: Cross-Language Android Permission Specification
Venue: arXiv cs.CR 2021
Year: 2021

The Android system manages access to sensitive APIs by permission enforcement. An application (app) must declare proper permissions before invoking specific Android APIs. However, there is no official documentation providing the complete list of permission-protected APIs and the corresponding permissions to date. Researchers have spent significant efforts extracting such API protection mapping from the Android API framework, which leverages static code analysis to determine if specific permissions are required before accessing an API. Nevertheless, none of them has attempted to analyze the protection mapping in the native library (i.e., code written in C and C++), an essential component of the Android framework that handles communication with the lower-level hardware, such as cameras and sensors. While the protection mapping can be utilized to detect various security vulnerabilities in Android apps, such as permission over-privilege and component hijacking, imprecise mapping will lead to false results in detecting such security vulnerabilities. To fill this gap, we develop a prototype system, named NatiDroid, to facilitate the cross-language static analysis to benchmark against two state-of-the-art tools, termed Axplorer and Arcade. We evaluate NatiDroid on more than 11,000 Android apps, including system apps from custom Android ROMs and third-party apps from the Google Play. Our NatiDroid can identify up to 464 new API-permission mappings, in contrast to the worst-case results derived from both Axplorer and Arcade, where approximately 71% apps have at least one false positive in permission over-privilege and up to 3.6% apps have at least one false negative in component hijacking. Additionally, we identify that 24 components with at least one Native-triggered component hijacking vulnerability are misidentified by two benchmarks.
Phase function estimation from a diffuse optical image via deep learning
Venue: arXiv cs.LG 2021
Year: 2021

The phase function is a key element of a light propagation model for Monte Carlo (MC) simulation, which is usually fitted with an analytic function with associated parameters. In recent years, machine learning methods were reported to estimate the parameters of the phase function of a particular form such as the Henyey-Greenstein phase function but, to our knowledge, no studies have been performed to determine the form of the phase function. Here we design a convolutional neural network to estimate the phase function from a diffuse optical image without any explicit assumption on the form of the phase function. Specifically, we use a Gaussian mixture model as an example to represent the phase function generally and learn the model parameters accurately. The Gaussian mixture model is selected because it provides the analytic expression of phase function to facilitate deflection angle sampling in MC simulation, and does not significantly increase the number of free parameters. Our proposed method is validated on MC-simulated reflectance images of typical biological tissues using the Henyey-Greenstein phase function with different anisotropy factors. The effects of field of view (FOV) and spatial resolution on the errors are analyzed to optimize the estimation method. The mean squared error of the phase function is 0.01 and the relative error of the anisotropy factor is 3.28%.
A Simple Algorithm for Computing the Zone of a Line in an Arrangement of Lines
Venue: arXiv cs.CG 2021
Year: 2021

Let $L$ be a set of $n$ lines in the plane. The zone $Z(\ell)$ of a line $\ell$ in the arrangement $\mathcal{A}(L)$ of $L$ is the set of faces of $\mathcal{A}(L)$ whose closure intersects $\ell$. It is known that the combinatorial size of $Z(\ell)$ is $O(n)$. Given $L$ and $\ell$, computing $Z(\ell)$ is a fundamental problem. Linear-time algorithms exist for computing $Z(\ell)$ if $\mathcal{A}(L)$ has already been built, but building $\mathcal{A}(L)$ takes $O(n^2)$ time. On the other hand, $O(n\log n)$-time algorithms are also known for computing $Z(\ell)$ without relying on $\mathcal{A}(L)$, but these algorithms are relatively complicated. In this paper, we present a simple algorithm that can compute $Z(\ell)$ in $O(n\log n)$ time. More specifically, once the sorted list of the intersections between $\ell$ and the lines of $L$ is known, the algorithm runs in $O(n)$ time. A big advantage of our algorithm, which mainly involves a Graham's scan style procedure, is its simplicity.
Larger Corner-Free Sets from Combinatorial Degenerations
Venue: arXiv cs.CC 2021
Year: 2021

There is a large and important collection of Ramsey-type combinatorial problems, closely related to central problems in complexity theory, that can be formulated in terms of the asymptotic growth of the size of the maximum independent sets in powers of a fixed small (directed or undirected) hypergraph, also called the Shannon capacity. An important instance of this is the corner problem studied in the context of multiparty communication complexity in the Number On the Forehead (NOF) model. Versions of this problem and the NOF connection have seen much interest (and progress) in recent works of Linial, Pitassi and Shraibman (ITCS 2019) and Linial and Shraibman (CCC 2021). We introduce and study a general algebraic method for lower bounding the Shannon capacity of directed hypergraphs via combinatorial degenerations, a combinatorial kind of "approximation" of subgraphs that originates from the study of matrix multiplication in algebraic complexity theory (and which play an important role there) but which we use in a novel way. Using the combinatorial degeneration method, we make progress on the corner problem by explicitly constructing a corner-free subset in $F_2^n \times F_2^n$ of size $Ω(3.39^n/poly(n))$, which improves the previous lower bound $Ω(2.82^n)$ of Linial, Pitassi and Shraibman (ITCS 2019) and which gets us closer to the best upper bound $4^{n - o(n)}$. Our new construction of corner-free sets implies an improved NOF protocol for the Eval problem. In the Eval problem over a group $G$, three players need to determine whether their inputs $x_1, x_2, x_3 \in G$ sum to zero. We find that the NOF communication complexity of the Eval problem over $F_2^n$ is at most $0.24n + O(\log n)$, which improves the previous upper bound $0.5n + O(\log n)$.
Accounting for Gaussian Process Imprecision in Bayesian Optimization
Venue: arXiv cs.AI 2021
Year: 2021

Bayesian optimization (BO) with Gaussian processes (GP) as surrogate models is widely used to optimize analytically unknown and expensive-to-evaluate functions. In this paper, we propose Prior-mean-RObust Bayesian Optimization (PROBO) that outperforms classical BO on specific problems. First, we study the effect of the Gaussian processes' prior specifications on classical BO's convergence. We find the prior's mean parameters to have the highest influence on convergence among all prior components. In response to this result, we introduce PROBO as a generalization of BO that aims at rendering the method more robust towards prior mean parameter misspecification. This is achieved by explicitly accounting for GP imprecision via a prior near-ignorance model. At the heart of this is a novel acquisition function, the generalized lower confidence bound (GLCB). We test our approach against classical BO on a real-world problem from material science and observe PROBO to converge faster. Further experiments on multimodal and wiggly target functions confirm the superiority of our method.
Choose Settings Carefully: Comparing Action Unit detection at Different Settings Using a Large-Scale Dataset
Venue: arXiv cs.CV 2021
Year: 2021

In this paper, we investigate the impact of some of the commonly used settings for (a) preprocessing face images, and (b) classification and training, on Action Unit (AU) detection performance and complexity. We use in our investigation a large-scale dataset, consisting of ~55K videos collected in the wild for participants watching commercial ads. The preprocessing settings include scaling the face to a fixed resolution, changing the color information (RGB to gray-scale), aligning the face, and cropping AU regions, while the classification and training settings include the kind of classifier (multi-label vs. binary) and the amount of data used for training models. To the best of our knowledge, no work had investigated the effect of those settings on AU detection. In our analysis we use CNNs as our baseline classification model.