OpenRaiser/Intern-Atlas huggingface dataset:
Refinement Type Directed Search for Meta-Interpretive-Learning of Higher-Order Logic Programs
Venue: arXiv cs.AI 2021
Year: 2021

The program synthesis problem within the Inductive Logic Programming (ILP) community has typically been seen as untyped. We consider the benefits of user provided types on background knowledge. Building on the Meta-Interpretive Learning (MIL) framework, we show that type checking is able to prune large parts of the hypothesis space of programs. The introduction of polymorphic type checking to the MIL approach to logic program synthesis is validated by strong theoretical and experimental results, showing a cubic reduction in the size of the search space and synthesis time, in terms of the number of typed background predicates. Additionally we are able to infer polymorphic types of synthesized clauses and of entire programs. The other advancement is in developing an approach to leveraging refinement types in ILP. Here we show that further pruning of the search space can be achieved, though the SMT solving used for refinement type checking comes
Ordinal relative belief entropy
Venue: arXiv cs.AI 2021
Year: 2021

Specially customised Entropies are widely applied in measuring the degree of uncertainties existing in the frame of discernment. However, all of these entropies regard the frame as a whole that has already been determined which dose not conform to actual situations. In real life, everything comes in an order, so how to measure uncertainties of the dynamic process of determining sequence of propositions contained in a frame of discernment is still an open issue and no related research has been proceeded. Therefore, a novel ordinal entropy to measure uncertainties of the frame of discernment considering the order of confirmation of propositions is proposed in this paper. Compared with traditional entropies, it manifests effects on degree of uncertainty brought by orders of propositions existing in a frame of discernment. Besides, some numerical examples are provided to verify the correctness and validity of the proposed entropy in this paper.
3D4ALL: Toward an Inclusive Pipeline to Classify 3D Contents
Venue: arXiv cs.HC 2021
Year: 2021

Algorithmic content moderation manages an explosive number of user-created content shared online everyday. Despite a massive number of 3D designs that are free to be downloaded, shared, and 3D printed by the users, detecting sensitivity with transparency and fairness has been controversial. Although sensitive 3D content might have a greater impact than other media due to its possible reproducibility and replicability without restriction, prevailed unawareness resulted in proliferation of sensitive 3D models online and a lack of discussion on transparent and fair 3D content moderation. As the 3D content exists as a document on the web mainly consisting of text and images, we first study the existing algorithmic efforts based on text and images and the prior endeavors to encompass transparency and fairness in moderation, which can also be useful in a 3D printing domain. At the same time, we identify 3D specific features that should be addressed to advance a 3D specialized algorithmic moderation. As a potential solution, we suggest a human-in-the-loop pipeline using augmented learning, powered by various stakeholders with different backgrounds and perspectives in understanding the content. Our pipeline aims to minimize personal biases by enabling diverse stakeholders to be vocal in reflecting various factors to interpret the content. We add our initial proposal for redesigning metadata of open 3D repositories, to invoke users' responsible actions of being granted consent from the subject upon sharing contents for free in the public spaces.
Online Learning for Unknown Partially Observable MDPs
Venue: arXiv cs.LG 2021
Year: 2021

Solving Partially Observable Markov Decision Processes (POMDPs) is hard. Learning optimal controllers for POMDPs when the model is unknown is harder. Online learning of optimal controllers for unknown POMDPs, which requires efficient learning using regret-minimizing algorithms that effectively tradeoff exploration and exploitation, is even harder, and no solution exists currently. In this paper, we consider infinite-horizon average-cost POMDPs with unknown transition model, though a known observation model. We propose a natural posterior sampling-based reinforcement learning algorithm (PSRL-POMDP) and show that it achieves a regret bound of $O(\log T)$, where $T$ is the time horizon, when the parameter set is finite. In the general case (continuous parameter set), we show that the algorithm achieves $O (T^{2/3})$ regret under two technical assumptions. To the best of our knowledge, this is the first online RL algorithm for POMDPs and has sub-linear regret.
New identities for the Shannon function and applications
Venue: arXiv cs.IT 2021
Year: 2021

We show how the Shannon entropy function H(p,q)is expressible as a linear combination of other Shannon entropy functions involving quotients of polynomials in p,q of degree n for any given positive integer n. An application to cryptographic keys is presented.
A Simulation-based End-to-End Learning Framework for Evidential Occupancy Grid Mapping
Venue: arXiv cs.RO 2021
Year: 2021

Evidential occupancy grid maps (OGMs) are a popular representation of the environment of automated vehicles. Inverse sensor models (ISMs) are used to compute OGMs from sensor data such as lidar point clouds. Geometric ISMs show a limited performance when estimating states in unobserved but inferable areas and have difficulties dealing with ambiguous input. Deep learning-based ISMs face the challenge of limited training data and they often cannot handle uncertainty quantification yet. We propose a deep learning-based framework for learning an OGM algorithm which is both capable of quantifying first- and second-order uncertainty and which does not rely on manually labeled data. Results on synthetic and on real-world data show superiority over other approaches. Source code and datasets are available at https://github.com/ika-rwth-aachen/EviLOG
No-Regret Reinforcement Learning with Heavy-Tailed Rewards
Venue: arXiv cs.LG 2021
Year: 2021

Reinforcement learning algorithms typically assume rewards to be sampled from light-tailed distributions, such as Gaussian or bounded. However, a wide variety of real-world systems generate rewards that follow heavy-tailed distributions. We consider such scenarios in the setting of undiscounted reinforcement learning. By constructing a lower bound, we show that the difficulty of learning heavy-tailed rewards asymptotically dominates the difficulty of learning transition probabilities. Leveraging techniques from robust mean estimation, we propose Heavy-UCRL2 and Heavy-Q-Learning, and show that they achieve near-optimal regret bounds in this setting. Our algorithms also naturally generalize to deep reinforcement learning applications; we instantiate Heavy-DQN as an example of this. We demonstrate that all of our algorithms outperform baselines on both synthetic MDPs and standard RL benchmarks.
Fragmented Objects: Boosting Concurrency of Shared Large Objects
Venue: arXiv cs.DC 2021
Year: 2021

This work examines strategies to handle large shared data objects in distributed storage systems (DSS), while boosting the number of concurrent accesses, maintaining strong consistency guarantees, and ensuring good operation performance. To this respect, we define the notion of fragmented objects:con-current objects composed of a list of fragments (or blocks) that allow operations to manipulate each of their fragments individually. As the fragments belong to the same object, it is not enough that each fragment is linearizable to have useful consistency guarantees in the composed object. Hence, we capture the consistency semantic of the whole object with the notion of fragmented linearizability. Then, considering that a variance of linearizability, coverability, is more suited for versioned objects like files, we provide an implementation of a distributed file system, called COBFS, that utilizes coverable fragmented objects (i.e., files).In COBFS, each file is a linked-list of coverable block objects. Preliminary emulation of COBFS demonstrates the potential of our approach in boosting the concurrency of strongly consistent large objects.
Revisiting Optimal Resilience of Fast Byzantine Consensus (Extended Version)
Venue: arXiv cs.DC 2021
Year: 2021

It is a common belief that Byzantine fault-tolerant solutions for consensus are significantly slower than their crash fault-tolerant counterparts. Indeed, in PBFT, the most widely known Byzantine fault-tolerant consensus protocol, it takes three message delays to decide a value, in contrast with just two in Paxos. This motivates the search for fast Byzantine consensus algorithms that can produce decisions after just two message delays \emph{in the common case}, e.g., under the assumption that the current leader is correct and not suspected by correct processes. The (optimal) two-step latency comes with the cost of lower resilience: fast Byzantine consensus requires more processes to tolerate the same number of faults. In particular, $5f+1$ processes were claimed to be necessary to tolerate $f$ Byzantine failures. In this paper, we present a fast Byzantine consensus algorithm that relies on just $5f-1$ processes. Moreover, we show that $5f-1$ is the tight lower bound, correcting a mistake in the earlier work. While the difference of just $2$ processes may appear insignificant for large values of $f$, it can be crucial for systems of a smaller scale. In particular, for $f=1$, our algorithm requires only $4$ processes, which is optimal for any (not necessarily fast) partially synchronous Byzantine consensus algorithm.
Deep Learning based Channel Extrapolation for Large-Scale Antenna Systems: Opportunities, Challenges and Solutions
Venue: arXiv cs.IT 2021
Year: 2021

With the depletion of spectrum, wireless communication systems turn to exploit large antenna arrays to achieve the degree of freedom in space domain, such as millimeter wave massive multi-input multioutput (MIMO), reconfigurable intelligent surface assisted communications and cell-free massive MIMO. In these systems, how to acquire accurate channel state information (CSI) is difficult and becomes a bottleneck of the communication links. In this article, we introduce the concept of channel extrapolation that relies on a small portion of channel parameters to infer the remaining channel parameters. Since the substance of channel extrapolation is a mapping from one parameter subspace to another, we can resort to deep learning (DL), a powerful learning architecture, to approximate such mapping function. Specifically, we first analyze the requirements, conditions and challenges for channel extrapolation. Then, we present three typical extrapolations over the antenna dimension, the frequency dimension, and the physical terminal, respectively. We also illustrate their respective principles, design challenges and DL strategies. It will be seen that channel extrapolation could greatly reduce the transmission overhead and subsequently enhance the performance gains compared with the traditional strategies. In the end, we provide several potential research directions on channel extrapolation for future intelligent communications systems.
Restoring Uniqueness in MicroVM Snapshots
Venue: arXiv cs.CR 2021
Year: 2021

Code initialization -- the step of loading code, executing static code, filling caches, and forming re-used connections -- tends to dominate cold-start time in serverless compute systems such as AWS Lambda. Post-initialization memory snapshots, cloned and restored on start, have emerged as a viable solution to this problem, with incremental snapshot and fast restore support in VMMs like Firecracker. Saving memory introduces the challenge of managing high-value memory contents, such as cryptographic secrets. Cloning introduces the challenge of restoring the uniqueness of the VMs, to allow them to do unique things like generate UUIDs, secrets, and nonces. This paper examines solutions to these problems in the every microsecond counts context of serverless cold-start, and discusses the state-of-the-art of available solutions. We present two new interfaces aimed at solving this problem -- MADV\_WIPEONSUSPEND and SysGenId -- and compare them to alternative solutions.
Blocks World Revisited: The Effect of Self-Occlusion on Classification by Convolutional Neural Networks
Venue: arXiv cs.CV 2021
Year: 2021

Despite the recent successes in computer vision, there remain new avenues to explore. In this work, we propose a new dataset to investigate the effect of self-occlusion on deep neural networks. With TEOS (The Effect of Self-Occlusion), we propose a 3D blocks world dataset that focuses on the geometric shape of 3D objects and their omnipresent challenge of self-occlusion. We designed TEOS to investigate the role of self-occlusion in the context of object classification. Even though remarkable progress has been seen in object classification, self-occlusion is a challenge. In the real-world, self-occlusion of 3D objects still presents significant challenges for deep learning approaches. However, humans deal with this by deploying complex strategies, for instance, by changing the viewpoint or manipulating the scene to gather necessary information. With TEOS, we present a dataset of two difficulty levels (L1 and L2 ), containing 36 and 12 objects, respectively. We provide 738 uniformly sampled views of each object, their mask, object and camera position, orientation, amount of self-occlusion, as well as the CAD model of each object. We present baseline evaluations with five well-known classification deep neural networks and show that TEOS poses a significant challenge for all of them. The dataset, as well as the pre-trained models, are made publicly available for the scientific community under https://nvision2.data.eecs.yorku.ca/TEOS.
Global Research Trends in the Modern Language Journal from 1999 to 2018: A Data-Driven Analysis
Venue: arXiv cs.DL 2021
Year: 2021

The present study conducts a scientometric study of the Modern Language Journal literature from 1999 to 2018 based on the database of Web of Science, 2018. A total of 2564 items resulted from the publication name using "Modern Language Journal" as the search term. Based on the number of publications during the study period no consistent growth is observed in the research activities pertaining to the journal. The annual distribution of publications, number of authors, institution productivity, country wise publications and Citations are analyzed. Highly productive authors, institutions, and countries are identified. The results reveal that the maximum number of papers 179 is published in the year 1999. It was also observed that Byrnes H is the most productive, contributed 51 publications and Kramsch C is most cited author in the field having 543 global citations. The highest number (38.26%) of publications, contributed from USA and the foremost productive establishment was University of Iowa.
Machine Learning-Based Optimal Mesh Generation in Computational Fluid Dynamics
Venue: arXiv cs.LG 2021
Year: 2021

Computational Fluid Dynamics (CFD) is a major sub-field of engineering. Corresponding flow simulations are typically characterized by heavy computational resource requirements. Often, very fine and complex meshes are required to resolve physical effects in an appropriate manner. Since all CFD algorithms scale at least linearly with the size of the underlying mesh discretization, finding an optimal mesh is key for computational efficiency. One methodology used to find optimal meshes is goal-oriented adaptive mesh refinement. However, this is typically computationally demanding and only available in a limited number of tools. Within this contribution, we adopt a machine learning approach to identify optimal mesh densities. We generate optimized meshes using classical methodologies and propose to train a convolutional network predicting optimal mesh densities given arbitrary geometries. The proposed concept is validated along 2d wind tunnel simulations with more than 60,000 simulations. Using a training set of 20,000 simulations we achieve accuracies of more than 98.7%. Corresponding predictions of optimal meshes can be used as input for any mesh generation and CFD tool. Thus without complex computations, any CFD engineer can start his predictions from a high quality mesh.
Structured Prediction for CRiSP Inverse Kinematics Learning with Misspecified Robot Models
Venue: arXiv cs.RO 2021
Year: 2021

With the recent advances in machine learning, problems that traditionally would require accurate modeling to be solved analytically can now be successfully approached with data-driven strategies. Among these, computing the inverse kinematics of a redundant robot arm poses a significant challenge due to the non-linear structure of the robot, the hard joint constraints and the non-invertible kinematics map. Moreover, most learning algorithms consider a completely data-driven approach, while often useful information on the structure of the robot is available and should be positively exploited. In this work, we present a simple, yet effective, approach for learning the inverse kinematics. We introduce a structured prediction algorithm that combines a data-driven strategy with the model provided by a forward kinematics function -- even when this function is misspecified -- to accurately solve the problem. The proposed approach ensures that predicted joint configurations are well within the robot's constraints. We also provide statistical guarantees on the generalization properties of our estimator as well as an empirical evaluation of its performance on trajectory reconstruction tasks.
The Power of $D$-hops in Matching Power-Law Graphs
Venue: arXiv cs.DS 2021
Year: 2021

This paper studies seeded graph matching for power-law graphs. Assume that two edge-correlated graphs are independently edge-sampled from a common parent graph with a power-law degree distribution. A set of correctly matched vertex-pairs is chosen at random and revealed as initial seeds. Our goal is to use the seeds to recover the remaining latent vertex correspondence between the two graphs. Departing from the existing approaches that focus on the use of high-degree seeds in $1$-hop neighborhoods, we develop an efficient algorithm that exploits the low-degree seeds in suitably-defined $D$-hop neighborhoods. Specifically, we first match a set of vertex-pairs with appropriate degrees (which we refer to as the first slice) based on the number of low-degree seeds in their $D$-hop neighborhoods. This significantly reduces the number of initial seeds needed to trigger a cascading process to match the rest of the graphs. Under the Chung-Lu random graph model with $n$ vertices, max degree $Θ(\sqrt{n})$, and the power-law exponent $2<β<3$, we show that as soon as $D> \frac{4-β}{3-β}$, by optimally choosing the first slice, with high probability our algorithm can correctly match a constant fraction of the true pairs without any error, provided with only $Ω((\log n)^{4-β})$ initial seeds. Our result achieves an exponential reduction in the seed size requirement, as the best previously known result requires $n^{1/2+ε}$ seeds (for any small constant $ε>0$). Performance evaluation with synthetic and real data further corroborates the improved performance of our algorithm.
Non-invasive Cognitive-level Human Interfacing for the Robotic Restoration of Reaching & Grasping
Venue: arXiv cs.RO 2021
Year: 2021

Assistive and Wearable Robotics have the potential to support humans with different types of motor impairments to become independent and fulfil their activities of daily living successfully. The success of these robot systems, however, relies on the ability to meaningfully decode human action intentions and carry them out appropriately. Neural interfaces have been explored for use in such system with several successes, however, they tend to be invasive and require training periods in the order of months. We present a robotic system for human augmentation, capable of actuating the user's arm and fingers for them, effectively restoring the capability of reaching, grasping and manipulating objects; controlled solely through the user's eye movements. We combine wearable eye tracking, the visual context of the environment and the structural grammar of human actions to create a cognitive-level assistive robotic setup that enables the users in fulfilling activities of daily living, while conserving interpretability, and the agency of the user. The interface is worn, calibrated and ready to use within 5 minutes. Users learn to control and make successful use of the system with an additional 5 minutes of interaction. The system is tested with 5 healthy participants, showing an average success rate of $96.6\%$ on first attempt across 6 tasks.
Towards Unbiased and Accurate Deferral to Multiple Experts
Venue: arXiv cs.LG 2021
Year: 2021

Machine learning models are often implemented in cohort with humans in the pipeline, with the model having an option to defer to a domain expert in cases where it has low confidence in its inference. Our goal is to design mechanisms for ensuring accuracy and fairness in such prediction systems that combine machine learning model inferences and domain expert predictions. Prior work on "deferral systems" in classification settings has focused on the setting of a pipeline with a single expert and aimed to accommodate the inaccuracies and biases of this expert to simultaneously learn an inference model and a deferral system. Our work extends this framework to settings where multiple experts are available, with each expert having their own domain of expertise and biases. We propose a framework that simultaneously learns a classifier and a deferral system, with the deferral system choosing to defer to one or more human experts in cases of input where the classifier has low confidence. We test our framework on a synthetic dataset and a content moderation dataset with biased synthetic experts, and show that it significantly improves the accuracy and fairness of the final predictions, compared to the baselines. We also collect crowdsourced labels for the content moderation task to construct a real-world dataset for the evaluation of hybrid machine-human frameworks and show that our proposed learning framework outperforms baselines on this real-world dataset as well.
Deep Adversarial Learning on Google Home devices
Venue: arXiv cs.CR 2021
Year: 2021

Smart speakers and voice-based virtual assistants are core components for the success of the IoT paradigm. Unfortunately, they are vulnerable to various privacy threats exploiting machine learning to analyze the generated encrypted traffic. To cope with that, deep adversarial learning approaches can be used to build black-box countermeasures altering the network traffic (e.g., via packet padding) and its statistical information. This letter showcases the inadequacy of such countermeasures against machine learning attacks with a dedicated experimental campaign on a real network dataset. Results indicate the need for a major re-engineering to guarantee the suitable protection of commercially available smart speakers.