OpenRaiser/Intern-Atlas huggingface dataset:
Autonomous Recharging and Flight Mission Planning for Battery-operated Autonomous Drones
Venue: arXiv cs.RO 2022
Year: 2022

Unmanned aerial vehicles (UAVs), commonly known as drones, are being increasingly deployed throughout the globe as a means to streamline monitoring, inspection, mapping, and logistic routines. When dispatched on autonomous missions, drones require an intelligent decision-making system for trajectory planning and tour optimization. Given the limited capacity of their onboard batteries, a key design challenge is to ensure the underlying algorithms can efficiently optimize the mission objectives along with recharging operations during long-haul flights. With this in view, the present work undertakes a comprehensive study on automated tour management systems for an energy-constrained drone: (1) We construct a machine learning model that estimates the energy expenditure of typical multi-rotor drones while accounting for real-world aspects and extrinsic meteorological factors. (2) Leveraging this model, the joint program of flight mission planning and recharging optimization is formulated as a multi-criteria Asymmetric Traveling Salesman Problem (ATSP), wherein a drone seeks for the time-optimal energy-feasible tour that visits all the target sites and refuels whenever necessary. (3) We devise an efficient approximation algorithm with provable worst-case performance guarantees and implement it in a drone management system, which supports real-time flight path tracking and re-computation in dynamic environments. (4) The effectiveness and practicality of the proposed approach are validated through extensive numerical simulations as well as real-world experiments.
Getting around the Halting Problem
Venue: arXiv cs.LO 2022
Year: 2022

There are numbers k and s and a URM program A(n,m) satisfying the following conditions. 1. If A(n,m) halts, then Cn(m) diverges. 2. For all n, C_k(n) = A(n,n) and C_s(n) = C_k(s). 3. A(k,s) halts and for all n, A(s,n) diverges. Here C_n(_) is a program with index n in some exhaustive enumeration of all possible programs. This has implications for solving the liar paradox and for generalization of Gödel incompleteness theorem to formal systems other than PA.
Deep CNN Framework for Audio Event Recognition using Weakly Labeled Web Data
Venue: arXiv cs.SD 2022
Year: 2022

The development of audio event recognition systems require labeled training data, which are generally hard to obtain. One promising source of recordings of audio events is the large amount of multimedia data on the web. In particular, if the audio content analysis must itself be performed on web audio, it is important to train the recognizers themselves from such data. Training from these web data, however, poses several challenges, the most important being the availability of labels: labels, if any, that may be obtained for the data are generally weak, and not of the kind conventionally required for training detectors or classifiers. We propose that learning algorithms that can exploit weak labels offer an effective method to learn from web data. We then propose a robust and efficient deep convolutional neural network (CNN) based framework to learn audio event recognizers from weakly labeled data. The proposed method can train from and analyze recordings of variable length in an efficient manner and outperforms a network trained with strongly labeled web data by a considerable margin. Moreover, even though we learn from weakly labeled data, where event time stamps within the recording are not available during training, our proposed framework is able to localize events during the inference stage.
Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
Venue: arXiv cs.DS 2022
Year: 2022

The Directed Steiner Network (DSN) problem takes as input a directed edge-weighted graph $G=(V,E)$ and a set $\mathcal{D}\subseteq V\times V$ of $k$ demand pairs. The aim is to compute the cheapest network $N\subseteq G$ for which there is an $s\to t$ path for each $(s,t)\in\mathcal{D}$. It is known that this problem is notoriously hard as there is no $k^{1/4-o(1)}$-approximation algorithm under Gap-ETH, even when parametrizing the runtime by $k$ [Dinur & Manurangsi, ITCS 2018]. In light of this, we systematically study several special cases of DSN and determine their parameterized approximability for the parameter $k$. For the bi-DSN$_\text{Planar}$ problem, the aim is to compute a solution $N\subseteq G$ whose cost is at most that of an optimum planar solution in a bidirected graph $G$, i.e., for every edge $uv$ of $G$ the reverse edge $vu$ exists and has the same weight. This problem is a generalization of several well-studied special cases. Our main result is that this problem admits a parameterized approximation scheme (PAS) for $k$. We also prove that our result is tight in the sense that (a) the runtime of our PAS cannot be significantly improved, and (b) it is unlikely that a PAS exists for any generalization of bi-DSN$_\text{Planar}$, unless FPT=W[1]. One important special case of DSN is the Strongly Connected Steiner Subgraph (SCSS) problem, for which the solution network $N\subseteq G$ needs to strongly connect a given set of $k$ terminals. It has been observed before that for SCSS a parameterized $2$-approximation exists when parameterized by $k$ [Chitnis et al., IPEC 2013]. We give a tight inapproximability result by showing that for $k$ no parameterized $(2-\varepsilon)$-approximation algorithm exists under Gap-ETH. Additionally we show that when restricting the input of SCSS to bidirected graphs, the problem remains NP-hard but becomes FPT for $k$.
On the mathematics of beauty: beautiful music
Venue: arXiv cs.IT 2022
Year: 2022

In this paper, we will study the simplest kind of beauty that can be found in a simple piece of music and can be appreciated universally. The proposed approach shows that aesthetically appealing patterns deliver higher amount of information over multiple levels in comparison with less aesthetically appealing patterns when the same amount of energy is used. The proposed model is tested on a set of beautiful music pieces.
Understanding tree: a tool for estimating one's understanding of conceptual knowledge
Venue: arXiv cs.DB 2022
Year: 2022

People learn whenever and wherever possible, and whatever they like or encounter--Mathematics, Drama, Art, Languages, Physics, Philosophy, and so on. With the bursting of knowledge, evaluation of one's understanding of conceptual knowledge becomes increasingly difficult. There are a lot of demands for evaluating one's understanding of a piece of knowledge, e.g., facilitating personalized recommendations; discovering one's expertises and deficiencies in a field; recommending topics for a conversation between people with different educational or cultural backgrounds in their first encounter; recommending a learning material to practice a meaningful learning etc. Assessment of understanding of knowledge is conventionally practiced through tests or interviews, but they have some limitations such as low-efficiency and in-comprehensive. We propose a method to estimate one's understanding of conceptual knowledge, by keeping track of his/her learning activities. It overcomes some limitations of traditional methods, hence complements traditional methods.
Language Design as Information Renormalization
Venue: arXiv cs.CL 2022
Year: 2022

Here we consider some well-known facts in syntax from a physics perspective, allowing us to establish equivalences between both fields with many consequences. Mainly, we observe that the operation MERGE, put forward by N. Chomsky in 1995, can be interpreted as a physical information coarse-graining. Thus, MERGE in linguistics entails information renormalization in physics, according to different time scales. We make this point mathematically formal in terms of language models. In this setting, MERGE amounts to a probability tensor implementing a coarse-graining, akin to a probabilistic context-free grammar. The probability vectors of meaningful sentences are given by stochastic tensor networks (TN) built from diagonal tensors and which are mostly loop-free, such as Tree Tensor Networks and Matrix Product States, thus being computationally very efficient to manipulate. We show that this implies the polynomially-decaying (long-range) correlations experimentally observed in language, and also provides arguments in favour of certain types of neural networks for language processing. Moreover, we show how to obtain such language models from quantum states that can be efficiently prepared on a quantum computer, and use this to find bounds on the perplexity of the probability distribution of words in a sentence. Implications of our results are discussed across several ambits.
Mechanism Redesign
Venue: arXiv cs.GT 2022
Year: 2022

This paper develops the theory of mechanism redesign by which an auctioneer can reoptimize an auction based on bid data collected from previous iterations of the auction on bidders from the same market. We give a direct method for estimation of the revenue of a counterfactual auction from the bids in the current auction. The estimator is a simple weighted order statistic of the bids and has the optimal error rate. Two applications of our estimator are A/B testing (a.k.a., randomized controlled trials) and instrumented optimization (i.e., revenue optimization subject to being able to do accurate inference of any counterfactual auction revenue).
Distances and Isomorphism between Networks: Stability and Convergence of Network Invariants
Venue: arXiv cs.DM 2022
Year: 2022

We develop the theoretical foundations of a generalized Gromov-Hausdorff distance between functions on networks that has recently been applied to various subfields of topological data analysis and optimal transport. These functional representations of networks, or networks for short, specialize in the finite setting to (possibly asymmetric) adjacency matrices and derived representations such as distance or kernel matrices. Existing literature utilizing these constructions cannot, however, benefit from continuous formulations because the continuum limits of finite networks under this distance are not well-understood. For example, while there are currently numerous persistent homology methods on finite networks, it is unclear if these methods produce well-defined persistence diagrams in the infinite setting. We resolve this situation by introducing the collection of compact networks that arises by taking continuum limits of finite networks and developing sampling results showing that this collection admits well-defined persistence diagrams. Compared to metric spaces, the isomorphism class of the generalized Gromov-Hausdorff distance over networks is rather complex, and contains representatives having different cardinalities and different topologies. We provide an exact characterization of a suitable notion of isomorphism for compact networks as well as alternative, stronger characterizations under additional topological regularity assumptions. Toward data applications, we describe a unified framework for developing quantitatively stable network invariants, provide basic examples, and cast existing results on the stability of persistent homology methods in this extended framework. To illustrate our theoretical results, we introduce a model of directed circles with finite reversibility and characterize their Dowker persistence diagrams.
On the Complexity of Robust Stable Marriage
Venue: arXiv cs.CC 2022
Year: 2022

Robust Stable Marriage (RSM) is a variant of the classical Stable Marriage problem, where the robustness of a given stable matching is measured by the number of modifications required for repairing it in case an unforeseen event occurs. We focus on the complexity of finding an (a,b)-supermatch. An (a,b)-supermatch is defined as a stable matching in which if any 'a' (non-fixed) men/women break up it is possible to find another stable matching by changing the partners of those 'a' men/women and also the partners of at most 'b' other couples. In order to show deciding if there exists an (a,b)-supermatch is NP-Complete, we first introduce a SAT formulation that is NP-Complete by using Schaefer's Dichotomy Theorem. Then, we show the equivalence between the SAT formulation and finding a (1,1)-supermatch on a specific family of instances.
Roaring Bitmaps: Implementation of an Optimized Software Library
Venue: arXiv cs.DB 2022
Year: 2022

Compressed bitmap indexes are used in systems such as Git or Oracle to accelerate queries. They represent sets and often support operations such as unions, intersections, differences, and symmetric differences. Several important systems such as Elasticsearch, Apache Spark, Netflix's Atlas, LinkedIn's Pinot, Metamarkets' Druid, Pilosa, Apache Hive, Apache Tez, Microsoft Visual Studio Team Services and Apache Kylin rely on a specific type of compressed bitmap index called Roaring. We present an optimized software library written in C implementing Roaring bitmaps: CRoaring. It benefits from several algorithms designed for the single-instruction-multiple-data (SIMD) instructions available on commodity processors. In particular, we present vectorized algorithms to compute the intersection, union, difference and symmetric difference between arrays. We benchmark the library against a wide range of competitive alternatives, identifying weaknesses and strengths in our software. Our work is available under a liberal open-source license.
Analyzing Material Recognition Performance of Thermal Tactile Sensing using a Large Materials Database and a Real Robot
Venue: arXiv cs.RO 2022
Year: 2022

In this paper we focus on analyzing the thermal modality of tactile sensing for material recognition using a large materials database. Many factors affect thermal recognition performance, including sensor noise, the initial temperatures of the sensor and the object, the thermal effusivities of the materials, and the duration of contact. To analyze the influence of these factors on thermal recognition, we used a semi-infinite solid based thermal model to simulate heat-transfer data from all the materials in the CES Edupack Level-1 database. We used support-vector machines (SVMs) to predict F1 scores for binary material recognition for 2346 material pairs. We also collected data using a real robot equipped with a thermal sensor and analyzed its material recognition performance on 66 real-world material pairs. Additionally, we analyzed the performance when the models were trained on the simulated data and tested on the real-robot data. Our models predicted the material recognition performance with a 0.980 F1 score for the simulated data, a 0.994 F1 score for real-world data with constant initial sensor temperatures, a 0.966 F1 score for real-world data with varied initial sensor temperatures, and a 0.815 F1 score for sim-to-real transfer. Finally, we present some guidelines on sensor design and parameter choice for thermal recognition based on the insights gained from these results that would hopefully enable robotics researchers to use this less-explored tactile sensing modality more effectively during physical human-robot and robot-object interactions. We release our simulated and real-robot datasets for further use by the robotics community.
General Strong Polarization
Venue: arXiv cs.IT 2022
Year: 2022

Arikan's exciting discovery of polar codes has provided an altogether new way to efficiently achieve Shannon capacity. Given a (constant-sized) invertible matrix $M$, a family of polar codes can be associated with this matrix and its ability to approach capacity follows from the {\em polarization} of an associated $[0,1]$-bounded martingale, namely its convergence in the limit to either $0$ or $1$. Arikan showed polarization of the martingale associated with the matrix $G_2 = \left(\begin{matrix} 1& 0 1& 1\end{matrix}\right)$ to get capacity achieving codes. His analysis was later extended to all matrices $M$ that satisfy an obvious necessary condition for polarization. While Arikan's theorem does not guarantee that the codes achieve capacity at small blocklengths, it turns out that a "strong" analysis of the polarization of the underlying martingale would lead to such constructions. Indeed for the martingale associated with $G_2$ such a strong polarization was shown in two independent works ([Guruswami and Xia, IEEE IT '15] and [Hassani et al., IEEE IT '14]), resolving a major theoretical challenge of the efficient attainment of Shannon capacity. In this work we extend the result above to cover martingales associated with all matrices that satisfy the necessary condition for (weak) polarization. In addition to being vastly more general, our proofs of strong polarization are also simpler and modular. Specifically, our result shows strong polarization over all prime fields and leads to efficient capacity-achieving codes for arbitrary symmetric memoryless channels. We show how to use our analyses to achieve exponentially small error probabilities at lengths inverse polynomial in the gap to capacity. Indeed we show that we can essentially match any error probability with lengths that are only inverse polynomial in the gap to capacity.
Automatic Translating between Ancient Chinese and Contemporary Chinese with Limited Aligned Corpora
Venue: arXiv cs.CL 2022
Year: 2022

The Chinese language has evolved a lot during the long-term development. Therefore, native speakers now have trouble in reading sentences written in ancient Chinese. In this paper, we propose to build an end-to-end neural model to automatically translate between ancient and contemporary Chinese. However, the existing ancient-contemporary Chinese parallel corpora are not aligned at the sentence level and sentence-aligned corpora are limited, which makes it difficult to train the model. To build the sentence level parallel training data for the model, we propose an unsupervised algorithm that constructs sentence-aligned ancient-contemporary pairs by using the fact that the aligned sentence pair shares many of the tokens. Based on the aligned corpus, we propose an end-to-end neural model with copying mechanism and local attention to translate between ancient and contemporary Chinese. Experiments show that the proposed unsupervised algorithm achieves 99.4% F1 score for sentence alignment, and the translation model achieves 26.95 BLEU from ancient to contemporary, and 36.34 BLEU from contemporary to ancient.
Thompson Sampling for Combinatorial Semi-Bandits
Venue: arXiv cs.LG 2022
Year: 2022

In this paper, we study the application of the Thompson sampling (TS) methodology to the stochastic combinatorial multi-armed bandit (CMAB) framework. We first analyze the standard TS algorithm for the general CMAB model when the outcome distributions of all the base arms are independent, and obtain a distribution-dependent regret bound of $O(m\log K_{\max}\log T / Δ_{\min})$, where $m$ is the number of base arms, $K_{\max}$ is the size of the largest super arm, $T$ is the time horizon, and $Δ_{\min}$ is the minimum gap between the expected reward of the optimal solution and any non-optimal solution. This regret upper bound is better than the $O(m(\log K_{\max})^2\log T / Δ_{\min})$ bound in prior works. Moreover, our novel analysis techniques can help to tighten the regret bounds of other existing UCB-based policies (e.g., ESCB), as we improve the method of counting the cumulative regret. Then we consider the matroid bandit setting (a special class of CMAB model), where we could remove the independence assumption across arms and achieve a regret upper bound that matches the lower bound. Except for the regret upper bounds, we also point out that one cannot directly replace the exact offline oracle (which takes the parameters of an offline problem instance as input and outputs the exact best action under this instance) with an approximation oracle in TS algorithm for even the classical MAB problem. Finally, we use some experiments to show the comparison between regrets of TS and other existing algorithms, the experimental results show that TS outperforms existing baselines.
Distributionally Linearizable Data Structures
Venue: arXiv cs.DC 2022
Year: 2022

Relaxed concurrent data structures have become increasingly popular, due to their scalability in graph processing and machine learning applications. Despite considerable interest, there exist families of natural, high performing randomized relaxed concurrent data structures, such as the popular MultiQueue pattern for implementing relaxed priority queue data structures, for which no guarantees are known in the concurrent setting. Our main contribution is in showing for the first time that, under a set of analytic assumptions, a family of relaxed concurrent data structures, including variants of MultiQueues, but also a new approximate counting algorithm we call the MultiCounter, provides strong probabilistic guarantees on the degree of relaxation with respect to the sequential specification, in arbitrary concurrent executions. We formalize these guarantees via a new correctness condition called distributional linearizability, tailored to concurrent implementations with randomized relaxations. Our result is based on a new analysis of an asynchronous variant of the classic power-of-two-choices load balancing algorithm, in which placement choices can be based on inconsistent, outdated information (this result may be of independent interest). We validate our results empirically, showing that the MultiCounter algorithm can implement scalable relaxed timestamps, which in turn can improve the performance of the classic TL2 transactional algorithm by up to 3 times, for some settings of parameters.
Data-driven Policy Transfer with Imprecise Perception Simulation
Venue: arXiv cs.RO 2022
Year: 2022

The paper presents a complete pipeline for learning continuous motion control policies for a mobile robot when only a non-differentiable physics simulator of robot-terrain interactions is available. The multi-modal state estimation of the robot is also complex and difficult to simulate, so we simultaneously learn a generative model which refines simulator outputs. We propose a coarse-to-fine learning paradigm, where the coarse motion planning is alternated with imitation learning and policy transfer to the real robot. The policy is jointly optimized with the generative model. We evaluate the method on a real-world platform in a batch of experiments.
Probabilistic Rewriting and Asymptotic Behaviour: on Termination and Unique Normal Forms
Venue: arXiv cs.LO 2022
Year: 2022

While a mature body of work supports the study of rewriting systems, abstract tools for Probabilistic Rewriting are still limited. In this paper we study the question of uniqueness of the result (unique limit distribution), and develop a set of proof techniques to analyze and compare reduction strategies. The goal is to have tools to support the operational analysis of probabilistic calculi (such as probabilistic lambda-calculi) where evaluation allows for different reduction choices (hence different reduction paths).
Normalization for planar string diagrams and a quadratic equivalence algorithm
Venue: arXiv cs.LO 2022
Year: 2022

In the graphical calculus of planar string diagrams, equality is generated by exchange moves, which swap the heights of adjacent vertices. We show that left- and right-handed exchanges each give strongly normalizing rewrite strategies for connected string diagrams. We use this result to give a linear-time solution to the equivalence problem in the connected case, and a quadratic solution in the general case. We also give a stronger proof of the Joyal-Street coherence theorem, settling Selinger's conjecture on recumbent isotopy.