OpenRaiser/Intern-Atlas huggingface dataset:
Zero-Shot Imitating Collaborative Manipulation Plans from YouTube Cooking Videos
Venue: arXiv cs.RO 2022
Year: 2022

People often watch videos on the web to learn how to cook new recipes, assemble furniture or repair a computer. We wish to enable robots with the very same capability. This is challenging; there is a large variation in manipulation actions and some videos even involve multiple persons, who collaborate by sharing and exchanging objects and tools. Furthermore, the learned representations need to be general enough to be transferable to robotic systems. On the other hand, previous work has shown that the space of human manipulation actions has a linguistic, hierarchical structure that relates actions to manipulated objects and tools. Building upon this theory of language for action, we propose a system for understanding and executing demonstrated action sequences from full-length, real-world cooking videos on the web. The system takes as input a new, previously unseen cooking video annotated with object labels and bounding boxes, and outputs a collaborative manipulation action plan for one or more robotic arms. We demonstrate performance of the system in a standardized dataset of 100 YouTube cooking videos, as well as in six full-length Youtube videos that include collaborative actions between two participants. We compare our system with a baseline system that consists of a state-of-the-art action detection baseline and show our system achieves higher action detection accuracy. We additionally propose an open-source platform for executing the learned plans in a simulation environment as well as with an actual robotic arm.
QubitHD: A Stochastic Acceleration Method for HD Computing-Based Machine Learning
Venue: arXiv cs.LG 2022
Year: 2022

Machine Learning algorithms based on Brain-inspired Hyperdimensional(HD) computing imitate cognition by exploiting statistical properties of high-dimensional vector spaces. It is a promising solution for achieving high energy efficiency in different machine learning tasks, such as classification, semi-supervised learning, and clustering. A weakness of existing HD computing-based ML algorithms is the fact that they have to be binarized to achieve very high energy efficiency. At the same time, binarized models reach lower classification accuracies. To solve the problem of the trade-off between energy efficiency and classification accuracy, we propose the QubitHD algorithm. It stochastically binarizes HD-based algorithms, while maintaining comparable classification accuracies to their non-binarized counterparts. The FPGA implementation of QubitHD provides a 65% improvement in terms of energy efficiency, and a 95% improvement in terms of training time, as compared to state-of-the-art HD-based ML algorithms. It also outperforms state-of-the-art low-cost classifiers (such as Binarized Neural Networks) in terms of speed and energy efficiency by an order of magnitude during training and inference.
Modular Termination for Second-Order Computation Rules and Application to Algebraic Effect Handlers
Venue: arXiv cs.SC 2022
Year: 2022

We present a new modular proof method of termination for second-order computation, and report its implementation SOL. The proof method is useful for proving termination of higher-order foundational calculi. To establish the method, we use a variation of semantic labelling translation and Blanqui's General Schema: a syntactic criterion of strong normalisation. As an application, we apply this method to show termination of a variant of call-by-push-value calculus with algebraic effects and effect handlers. We also show that our tool SOL is effective to solve higher-order termination problems.
Group Fairness in Bandit Arm Selection
Venue: arXiv cs.LG 2022
Year: 2022

We propose a novel formulation of group fairness with biased feedback in the contextual multi-armed bandit (CMAB) setting. In the CMAB setting, a sequential decision maker must, at each time step, choose an arm to pull from a finite set of arms after observing some context for each of the potential arm pulls. In our model, arms are partitioned into two or more sensitive groups based on some protected feature(s) (e.g., age, race, or socio-economic status). Initial rewards received from pulling an arm may be distorted due to some unknown societal or measurement bias. We assume that in reality these groups are equal despite the biased feedback received by the agent. To alleviate this, we learn a societal bias term which can be used to both find the source of bias and to potentially fix the problem outside of the algorithm. We provide a novel algorithm that can accommodate this notion of fairness for an arbitrary number of groups, and provide a theoretical bound on the regret for our algorithm. We validate our algorithm using synthetic data and two real-world datasets for intervention settings wherein we want to allocate resources fairly across groups.
Reinforcement Learning-based Visual Navigation with Information-Theoretic Regularization
Venue: arXiv cs.RO 2022
Year: 2022

To enhance the cross-target and cross-scene generalization of target-driven visual navigation based on deep reinforcement learning (RL), we introduce an information-theoretic regularization term into the RL objective. The regularization maximizes the mutual information between navigation actions and visual observation transforms of an agent, thus promoting more informed navigation decisions. This way, the agent models the action-observation dynamics by learning a variational generative model. Based on the model, the agent generates (imagines) the next observation from its current observation and navigation target. This way, the agent learns to understand the causality between navigation actions and the changes in its observations, which allows the agent to predict the next action for navigation by comparing the current and the imagined next observations. Cross-target and cross-scene evaluations on the AI2-THOR framework show that our method attains at least a $10\%$ improvement of average success rate over some state-of-the-art models. We further evaluate our model in two real-world settings: navigation in unseen indoor scenes from a discrete Active Vision Dataset (AVD) and continuous real-world environments with a TurtleBot.We demonstrate that our navigation model is able to successfully achieve navigation tasks in these scenarios. Videos and models can be found in the supplementary material.
High-precision Estimation of Random Walks in Small Space
Venue: arXiv cs.CC 2022
Year: 2022

We provide a deterministic $\tilde{O}(\log N)$-space algorithm for estimating random walk probabilities on undirected graphs, and more generally Eulerian directed graphs, to within inverse polynomial additive error ($ε=1/\mathrm{poly}(N)$) where $N$ is the length of the input. Previously, this problem was known to be solvable by a randomized algorithm using space $O(\log N)$ (following Aleliunas et al., FOCS 79) and by a deterministic algorithm using space $O(\log^{3/2} N)$ (Saks and Zhou, FOCS 95 and JCSS 99), both of which held for arbitrary directed graphs but had not been improved even for undirected graphs. We also give improvements on the space complexity of both of these previous algorithms for non-Eulerian directed graphs when the error is negligible ($ε=1/N^{ω(1)}$), generalizing what Hoza and Zuckerman (FOCS 18) recently showed for the special case of distinguishing whether a random walk probability is $0$ or greater than $ε$. We achieve these results by giving new reductions between powering Eulerian random-walk matrices and inverting Eulerian Laplacian matrices, providing a new notion of spectral approximation for Eulerian graphs that is preserved under powering, and giving the first deterministic $\tilde{O}(\log N)$-space algorithm for inverting Eulerian Laplacian matrices. The latter algorithm builds on the work of Murtagh et al. (FOCS 17) that gave a deterministic $\tilde{O}(\log N)$-space algorithm for inverting undirected Laplacian matrices, and the work of Cohen et al. (FOCS 19) that gave a randomized $\tilde{O}(N)$-time algorithm for inverting Eulerian Laplacian matrices. A running theme throughout these contributions is an analysis of "cycle-lifted graphs", where we take a graph and "lift" it to a new graph whose adjacency matrix is the tensor product of the original adjacency matrix and a directed cycle (or variants of one).
FISR: Deep Joint Frame Interpolation and Super-Resolution with a Multi-scale Temporal Loss
Venue: arXiv cs.CV 2022
Year: 2022

Super-resolution (SR) has been widely used to convert low-resolution legacy videos to high-resolution (HR) ones, to suit the increasing resolution of displays (e.g. UHD TVs). However, it becomes easier for humans to notice motion artifacts (e.g. motion judder) in HR videos being rendered on larger-sized display devices. Thus, broadcasting standards support higher frame rates for UHD (Ultra High Definition) videos (4K@60 fps, 8K@120 fps), meaning that applying SR only is insufficient to produce genuine high quality videos. Hence, to up-convert legacy videos for realistic applications, not only SR but also video frame interpolation (VFI) is necessitated. In this paper, we first propose a joint VFI-SR framework for up-scaling the spatio-temporal resolution of videos from 2K 30 fps to 4K 60 fps. For this, we propose a novel training scheme with a multi-scale temporal loss that imposes temporal regularization on the input video sequence, which can be applied to any general video-related task. The proposed structure is analyzed in depth with extensive experiments.
Exploration and Coordination of Complementary Multi-Robot Teams in a Hunter and Gatherer Scenario
Venue: arXiv cs.MA 2022
Year: 2022

The hunter and gatherer approach copes with the problem of dynamic multi-robot task allocation, where tasks are unknowingly distributed over an environment. This approach employs two complementary teams of agents: one agile in exploring (hunters) and another dexterous in completing (gatherers) the tasks. Although this approach has been studied from the task planning point of view in our previous works, the multi-robot exploration and coordination aspects of the problem remain uninvestigated. This paper proposes a multi-robot exploration algorithm for hunters based on innovative notions of "expected information gain" to minimize the collective cost of task accomplishments in a distributed manner. Besides, we present a coordination solution between hunters and gatherers by integrating the novel notion of profit margins into the concept of expected information gain. Statistical analysis of extensive simulation results confirms the efficacy of the proposed algorithms compared in different environments with varying levels of obstacles complexities. We also demonstrate that the lack of effective coordination between hunters and gatherers significantly hurts the total effectiveness of the planning, especially in environments containing dense obstacles and confined corridors. Finally, it is statistically proven that the overall workload is distributed equally for each type of agent which ensures that the proposed solution is not biased to a particular agent and all agents behave analogously under similar characteristics.
Algorithms that "Don't See Color": Comparing Biases in Lookalike and Special Ad Audiences
Venue: arXiv cs.CY 2022
Year: 2022

Researchers and journalists have repeatedly shown that algorithms commonly used in domains such as credit, employment, healthcare, or criminal justice can have discriminatory effects. Some organizations have tried to mitigate these effects by simply removing sensitive features from an algorithm's inputs. In this paper, we explore the limits of this approach using a unique opportunity. In 2019, Facebook agreed to settle a lawsuit by removing certain sensitive features from inputs of an algorithm that identifies users similar to those provided by an advertiser for ad targeting, making both the modified and unmodified versions of the algorithm available to advertisers. We develop methodologies to measure biases along the lines of gender, age, and race in the audiences created by this modified algorithm, relative to the unmodified one. Our results provide experimental proof that merely removing demographic features from a real-world algorithmic system's inputs can fail to prevent biased outputs. As a result, organizations using algorithms to help mediate access to important life opportunities should consider other approaches to mitigating discriminatory effects.
Establishing a Search String to Detect Secondary Studies in Software Engineering
Venue: arXiv cs.SE 2022
Year: 2022

Context: A tertiary study can be performed to identify related reviews on a topic of interest. However, the elaboration of an appropriate and effective search string to detect secondary studies is challenging for Software Engineering (SE) researchers. Objective: The main goal of this study is to propose a suitable search string to detect secondary studies in SE, addressing issues such as the quantity of applied terms, relevance, recall and precision. Method: We analyzed seven tertiary studies under two perspectives: (1) structure -- strings' terms to detect secondary studies; and (2) field: where searching -- titles alone or abstracts alone or titles and abstracts together, among others. We validate our string by performing a two-step validation process. Firstly, we evaluated the capability to retrieve secondary studies over a set of 1537 secondary studies included in 24 tertiary studies in SE. Secondly, we evaluated the general capacity of retrieving secondary studies over an automated search using the Scopus digital library. Results: Our string was capable to retrieve an optimum value of over 90\% of the included secondary studies (recall) with a high general precision of almost 60\%. Conclusion: The suitable search string for finding secondary studies in SE contains the terms "systematic review", "literature review", "systematic mapping", "mapping study" and "systematic map".
A Fair Comparison of Graph Neural Networks for Graph Classification
Venue: arXiv cs.LG 2022
Year: 2022

Experimental reproducibility and replicability are critical topics in machine learning. Authors have often raised concerns about their lack in scientific publications to improve the quality of the field. Recently, the graph representation learning field has attracted the attention of a wide research community, which resulted in a large stream of works. As such, several Graph Neural Network models have been developed to effectively tackle graph classification. However, experimental procedures often lack rigorousness and are hardly reproducible. Motivated by this, we provide an overview of common practices that should be avoided to fairly compare with the state of the art. To counter this troubling trend, we ran more than 47000 experiments in a controlled and uniform framework to re-evaluate five popular models across nine common benchmarks. Moreover, by comparing GNNs with structure-agnostic baselines we provide convincing evidence that, on some datasets, structural information has not been exploited yet. We believe that this work can contribute to the development of the graph learning field, by providing a much needed grounding for rigorous evaluations of graph classification models.
Acoustic Scene Analysis using Analog Spiking Neural Network
Venue: arXiv cs.NE 2022
Year: 2022

Sensor nodes in a wireless sensor network (WSN) for security surveillance applications should preferably be small, energy-efficient, and inexpensive with in-sensor computational abilities. An appropriate data processing scheme in the sensor node reduces the power dissipation of the transceiver through the compression of information to be communicated. This study attempted a simulation-based analysis of human footstep sound classification in natural surroundings using simple time-domain features. The spiking neural network (SNN), a computationally low-weight classifier derived from an artificial neural network (ANN), was used to classify acoustic sounds. The SNN and required feature extraction schemes are amenable to low-power subthreshold analog implementation. The results show that all analog implementations of the proposed SNN scheme achieve significant power savings over the digital implementation of the same computing scheme and other conventional digital architectures using frequency-domain feature extraction and ANN-based classification. The algorithm is tolerant of the impact of process variations, which are inevitable in analog design, owing to the approximate nature of the data processing involved in such applications. Although SNN provides low-power operation at the algorithm level itself, ANN to SNN conversion leads to an unavoidable loss of classification accuracy of ~5%. We exploited the low-power operation of the analog processing SNN module by applying redundancy and majority voting, which improved the classification accuracy, taking it close to the ANN model.
Partitioning algorithms for weighted trees and cactus graphs
Venue: arXiv cs.DS 2022
Year: 2022

In this paper, we consider different constrained partition problems for weighted trees and cactus graphs. We focus on the (l,u)-partition problem, which is the problem of partitioning a weighted graph into connected clusters such that each cluster fulfills the lower and upper weight constraints l and u. Partitioning into a minimum, maximum or a fixed number of clusters is known to be NP-hard in general, but polynomial-time solvable on trees. We prove that these three variants of the (l,u)-partition problem can be solved for cactus graphs as well by presenting a polynomial-time algorithm. Additionally, we present an efficient method to compute the corresponding partitions. For other optimization goals or additional constraints, the partition problem becomes NP-hard - even on trees and for a lower weight bound equal to zero. We show that our method can be used as an algorithmic framework to solve other partition problems for weighted trees and cactus graphs with a pseudopolynomial runtime.
Facial Emotions Recognition using Convolutional Neural Net
Venue: arXiv cs.CV 2022
Year: 2022

Facial expressions vary from person to person, and the brightness, contrast, and resolution of every random image are different. This is why recognizing facial expressions is very difficult. This article proposes an efficient system for facial emotion recognition for the seven basic human emotions (angry, disgust, fear, happy, sad, surprise, and neutral), using a convolution neural network (CNN), which predicts and assigns probabilities to each emotion. Since deep learning models learn from data, thus, our proposed system processes each image with various pre-processing steps for better prediction. Every image was first passed through the face detection algorithm to include in the training dataset. As CNN requires a large amount of data, we duplicated our data using various filters on each image. Pre-processed images of size 80*100 are passed as input to the first layer of CNN. Three convolutional layers were used, followed by a pooling layer and three dense layers. The dropout rate for the dense layer was 20%. The model was trained by combining two publicly available datasets, JAFFE and KDEF. 90% of the data was used for training, while 10% was used for testing. We achieved maximum accuracy of 78.1 % using the combined dataset. Moreover, we designed an application of the proposed system with a graphical user interface that classifies emotions in real-time.
Understanding the QuickXPlain Algorithm: Simple Explanation and Formal Proof
Venue: arXiv cs.AI 2022
Year: 2022

In his seminal paper of 2004, Ulrich Junker proposed the QuickXPlain algorithm, which provides a divide-and-conquer computation strategy to find within a given set an irreducible subset with a particular (monotone) property. Beside its original application in the domain of constraint satisfaction problems, the algorithm has since then found widespread adoption in areas as different as model-based diagnosis, recommender systems, verification, or the Semantic Web. This popularity is due to the frequent occurrence of the problem of finding irreducible subsets on the one hand, and to QuickXPlain's general applicability and favorable computational complexity on the other hand. However, although (we regularly experience) people are having a hard time understanding QuickXPlain and seeing why it works correctly, a proof of correctness of the algorithm has never been published. This is what we account for in this work, by explaining QuickXPlain in a novel tried and tested way and by presenting an intelligible formal proof of it. Apart from showing the correctness of the algorithm and excluding the later detection of errors (proof and trust effect), the added value of the availability of a formal proof is, e.g., (i) that the workings of the algorithm often become completely clear only after studying, verifying and comprehending the proof (didactic effect), (ii) the shown proof methodology can be used as a guidance for proving other recursive algorithms (transfer effect), and (iii) the possibility of providing "gapless" correctness proofs of systems that rely on (results computed by) QuickXPlain, such as numerous model-based debuggers (completeness effect).
Generating Semantic Adversarial Examples via Feature Manipulation
Venue: arXiv cs.LG 2022
Year: 2022

The vulnerability of deep neural networks to adversarial attacks has been widely demonstrated (e.g., adversarial example attacks). Traditional attacks perform unstructured pixel-wise perturbation to fool the classifier. An alternative approach is to have perturbations in the latent space. However, such perturbations are hard to control due to the lack of interpretability and disentanglement. In this paper, we propose a more practical adversarial attack by designing structured perturbation with semantic meanings. Our proposed technique manipulates the semantic attributes of images via the disentangled latent codes. The intuition behind our technique is that images in similar domains have some commonly shared but theme-independent semantic attributes, e.g. thickness of lines in handwritten digits, that can be bidirectionally mapped to disentangled latent codes. We generate adversarial perturbation by manipulating a single or a combination of these latent codes and propose two unsupervised semantic manipulation approaches: vector-based disentangled representation and feature map-based disentangled representation, in terms of the complexity of the latent codes and smoothness of the reconstructed images. We conduct extensive experimental evaluations on real-world image data to demonstrate the power of our attacks for black-box classifiers. We further demonstrate the existence of a universal, image-agnostic semantic adversarial example.