OpenRaiser/Intern-Atlas huggingface dataset:
Paraconsistent Foundations for Probabilistic Reasoning, Programming and Concept Formation
Venue: arXiv cs.AI 2021
Year: 2021

It is argued that 4-valued paraconsistent truth values (called here "p-bits") can serve as a conceptual, mathematical and practical foundation for highly AI-relevant forms of probabilistic logic and probabilistic programming and concept formation. First it is shown that appropriate averaging-across-situations and renormalization of 4-valued p-bits operating in accordance with Constructible Duality (CD) logic yields PLN (Probabilistic Logic Networks) strength-and-confidence truth values. Then variations on the Curry-Howard correspondence are used to map these paraconsistent and probabilistic logics into probabilistic types suitable for use within dependent type based programming languages. Zach Weber's paraconsistent analysis of the sorites paradox is extended to form a paraconsistent / probabilistic / fuzzy analysis of concept boundaries; and a paraconsistent version of concept formation via Formal Concept Analysis is presented, building on a definition of fuzzy property-value degrees in terms of relative entropy on paraconsistent probability distributions. These general points are fleshed out via reference to the realization of probabilistic reasoning and programming and concept formation in the OpenCog AGI framework which is centered on collaborative multi-algorithm updating of a common knowledge metagraph.
Reinforcement Learning for Control of Valves
Venue: arXiv cs.LG 2021
Year: 2021

This paper is a study of reinforcement learning (RL) as an optimal-control strategy for control of nonlinear valves. It is evaluated against the PID (proportional-integral-derivative) strategy, using a unified framework. RL is an autonomous learning mechanism that learns by interacting with its environment. It is gaining increasing attention in the world of control systems as a means of building optimal-controllers for challenging dynamic and nonlinear processes. Published RL research often uses open-source tools (Python and OpenAI Gym environments). We use MATLAB's recently launched (R2019a) Reinforcement Learning Toolbox to develop the valve controller; trained using the DDPG (Deep Deterministic Policy-Gradient) algorithm and Simulink to simulate the nonlinear valve and create the experimental test-bench for evaluation. Simulink allows industrial engineers to quickly adapt and experiment with other systems of their choice. Results indicate that the RL controller is extremely good at tracking the signal with speed and produces a lower error with respect to the reference signal. The PID, however, is better at disturbance rejection and hence provides a longer life for the valves. Successful machine learning involves tuning many hyperparameters requiring significant investment of time and efforts. We introduce "Graded Learning" as a simplified, application oriented adaptation of the more formal and algorithmic "Curriculum for Reinforcement Learning". It is shown via experiments that it helps converge the learning task of complex non-linear real world systems. Finally, experiential learnings gained from this research are corroborated against published research.
Code Summarization with Structure-induced Transformer
Venue: arXiv cs.CL 2021
Year: 2021

Code summarization (CS) is becoming a promising area in recent language understanding, which aims to generate sensible human language automatically for programming language in the format of source code, serving in the most convenience of programmer developing. It is well known that programming languages are highly structured. Thus previous works attempt to apply structure-based traversal (SBT) or non-sequential models like Tree-LSTM and graph neural network (GNN) to learn structural program semantics. However, it is surprising that incorporating SBT into advanced encoder like Transformer instead of LSTM has been shown no performance gain, which lets GNN become the only rest means modeling such necessary structural clue in source code. To release such inconvenience, we propose structure-induced Transformer, which encodes sequential code inputs with multi-view structural clues in terms of a newly-proposed structure-induced self-attention mechanism. Extensive experiments show that our proposed structure-induced Transformer helps achieve new state-of-the-art results on benchmarks.
The Price is (Probably) Right: Learning Market Equilibria from Samples
Venue: arXiv cs.GT 2021
Year: 2021

Equilibrium computation in markets usually considers settings where player valuation functions are known. We consider the setting where player valuations are unknown; using a PAC learning-theoretic framework, we analyze some classes of common valuation functions, and provide algorithms which output direct PAC equilibrium allocations, not estimates based on attempting to learn valuation functions. Since there exist trivial PAC market outcomes with an unbounded worst-case efficiency loss, we lower-bound the efficiency of our algorithms. While the efficiency loss under general distributions is rather high, we show that in some cases (e.g., unit-demand valuations), it is possible to find a PAC market equilibrium with significantly better utility.
SALA: Soft Assignment Local Aggregation for Parameter Efficient 3D Semantic Segmentation
Venue: arXiv cs.CV 2021
Year: 2021

In this work, we focus on designing a point local aggregation function that yields parameter efficient networks for 3D point cloud semantic segmentation. We explore the idea of using learnable neighbor-to-grid soft assignment in grid-based aggregation functions. Previous methods in literature operate on a predefined geometric grid such as local volume partitions or irregular kernel points. A more general alternative is to allow the network to learn an assignment function that best suits the end task. Since it is learnable, this mapping is allowed to be different per layer instead of being applied uniformly throughout the depth of the network. By endowing the network with the flexibility to learn its own neighbor-to-grid assignment, we arrive at parameter efficient models that achieve state-of-the-art (SOTA) performance on S3DIS with at least 10$\times$ less parameters than the current reigning method. We also demonstrate competitive performance on ScanNet and PartNet compared with much larger SOTA models.
UNSAIL: Thwarting Oracle-Less Machine Learning Attacks on Logic Locking
Venue: arXiv cs.CR 2021
Year: 2021

Logic locking aims to protect the intellectual property (IP) of integrated circuit (IC) designs throughout the globalized supply chain. The SAIL attack, based on tailored machine learning (ML) models, circumvents combinational logic locking with high accuracy and is amongst the most potent attacks as it does not require a functional IC acting as an oracle. In this work, we propose UNSAIL, a logic locking technique that inserts key-gate structures with the specific aim to confuse ML models like those used in SAIL. More specifically, UNSAIL serves to prevent attacks seeking to resolve the structural transformations of synthesis-induced obfuscation, which is an essential step for logic locking. Our approach is generic; it can protect any local structure of key-gates against such ML-based attacks in an oracle-less setting. We develop a reference implementation for the SAIL attack and launch it on both traditionally locked and UNSAIL-locked designs. In SAIL, a change-prediction model is used to determine which key-gate structures to restore using a reconstruction model. Our study on benchmarks ranging from the ISCAS-85 and ITC-99 suites to the OpenRISC Reference Platform System-on-Chip (ORPSoC) confirms that UNSAIL degrades the accuracy of the change-prediction model and the reconstruction model by an average of 20.13 and 17 percentage points (pp) respectively. When the aforementioned models are combined, which is the most powerful scenario for SAIL, UNSAIL reduces the attack accuracy of SAIL by an average of 11pp. We further demonstrate that UNSAIL thwarts other oracle-less attacks, i.e., SWEEP and the redundancy attack, indicating the generic nature and strength of our approach. Detailed layout-level evaluations illustrate that UNSAIL incurs minimal area and power overheads of 0.26% and 0.61%, respectively, on the million-gate ORPSoC design.
A Versatile Keyframe-Based Structureless Filter for Visual Inertial Odometry
Venue: arXiv cs.RO 2021
Year: 2021

Motion estimation by fusing data from at least a camera and an Inertial Measurement Unit (IMU) enables many applications in robotics. However, among the multitude of Visual Inertial Odometry (VIO) methods, few efficiently estimate device motion with consistent covariance, and calibrate sensor parameters online for handling data from consumer sensors. This paper addresses the gap with a Keyframe-based Structureless Filter (KSF). For efficiency, landmarks are not included in the filter's state vector. For robustness, KSF associates feature observations and manages state variables using the concept of keyframes. For flexibility, KSF supports anytime calibration of IMU systematic errors, as well as extrinsic, intrinsic, and temporal parameters of each camera. Estimator consistency and observability of sensor parameters were analyzed by simulation. Sensitivity to design options, e.g., feature matching method and camera count was studied with the EuRoC benchmark. Sensor parameter estimation was evaluated on raw TUM VI sequences and smartphone data. Moreover, pose estimation accuracy was evaluated on EuRoC and TUM VI sequences versus recent VIO methods. These tests confirm that KSF reliably calibrates sensor parameters when the data contain adequate motion, and consistently estimate motion with accuracy rivaling recent VIO methods. Our implementation runs at 42 Hz with stereo camera images on a consumer laptop.
Corrected CBOW Performs as well as Skip-gram
Venue: arXiv cs.CL 2021
Year: 2021

Mikolov et al. (2013a) observed that continuous bag-of-words (CBOW) word embeddings tend to underperform Skip-gram (SG) embeddings, and this finding has been reported in subsequent works. We find that these observations are driven not by fundamental differences in their training objectives, but more likely on faulty negative sampling CBOW implementations in popular libraries such as the official implementation, word2vec.c, and Gensim. We show that after correcting a bug in the CBOW gradient update, one can learn CBOW word embeddings that are fully competitive with SG on various intrinsic and extrinsic tasks, while being many times faster to train.
From Semantic Communication to Semantic-aware Networking: Model, Architecture, and Open Problems
Venue: arXiv cs.NI 2021
Year: 2021

Existing communication systems are mainly built based on Shannon's information theory which deliberately ignores the semantic aspects of communication. The recent iteration of wireless technology, the so-called 5G and beyond, promises to support a plethora of services enabled by carefully tailored network capabilities based on the contents, requirements, as well as semantics. This sparkled significant interest in the semantic communication, a novel paradigm that involves the meaning of message into the communication. In this article, we first review the classic semantic communication framework and then summarize key challenges that hinder its popularity. We observe that some semantic communication processes such as semantic detection, knowledge modeling, and coordination, can be resource-consuming and inefficient, especially for the communication between a single source and a destination. We therefore propose a novel architecture based on federated edge intelligence for supporting resource-efficient semantic-aware networking. Our architecture allows each user to offload the computationally intensive semantic encoding and decoding tasks to the edge servers and protect its proprietary model-related information by coordinating via intermediate results. Our simulation result shows that the proposed architecture can reduce the resource consumption and significantly improve the communication efficiency.
Automatic Synthesis of Parallel Unix Commands and Pipelines with KumQuat
Venue: arXiv cs.PL 2021
Year: 2021

We present KumQuat, a system for automatically generating data parallel implementations of Unix shell commands and pipelines. The generated parallel versions split input streams, execute multiple instantiations of the original pipeline commands to process the splits in parallel, then combine the resulting parallel outputs to produce the final output stream. KumQuat automatically synthesizes the combine operators, with a domain-specific combiner language acting as a strong regularizer that promotes efficient inference of correct combiners. We evaluate KumQuat on 70 benchmark scripts that together have a total of 427 stages. KumQuat synthesizes a correct combiner for 113 of the 121 unique commands that appear in these benchmark scripts. The synthesis times vary between 39 seconds and 331 seconds with a median of 60 seconds. We present experimental results that show that these combiners enable the effective parallelization of our benchmark scripts.
Super-k: A Piecewise Linear Classifier Based on Voronoi Tessellations
Venue: arXiv cs.LG 2021
Year: 2021

Voronoi tessellations are used to partition the Euclidean space into polyhedral regions, which are called Voronoi cells. Labeling the Voronoi cells with the class information, we can map any classification problem into a Voronoi tessellation. In this way, the classification problem changes into a query of just finding the enclosing Voronoi cell. In order to accomplish this task, we have developed a new algorithm which generates a labeled Voronoi tessellation that partitions the training data into polyhedral regions and obtains interclass boundaries as an indirect result. It is called Supervised k-Voxels or in short Super-k. We are introducing Super-k as a foundational new algorithm and opening the possibility of a new family of algorithms. In this paper, it is shown via comparisons on certain datasets that the Super-k algorithm has the potential of providing comparable performance of the well-known SVM family of algorithms with less complexity.
AraELECTRA: Pre-Training Text Discriminators for Arabic Language Understanding
Venue: arXiv cs.CL 2021
Year: 2021

Advances in English language representation enabled a more sample-efficient pre-training task by Efficiently Learning an Encoder that Classifies Token Replacements Accurately (ELECTRA). Which, instead of training a model to recover masked tokens, it trains a discriminator model to distinguish true input tokens from corrupted tokens that were replaced by a generator network. On the other hand, current Arabic language representation approaches rely only on pretraining via masked language modeling. In this paper, we develop an Arabic language representation model, which we name AraELECTRA. Our model is pretrained using the replaced token detection objective on large Arabic text corpora. We evaluate our model on multiple Arabic NLP tasks, including reading comprehension, sentiment analysis, and named-entity recognition and we show that AraELECTRA outperforms current state-of-the-art Arabic language representation models, given the same pretraining data and with even a smaller model size.
Fast WordPiece Tokenization
Venue: arXiv cs.CL 2021
Year: 2021

Tokenization is a fundamental preprocessing step for almost all NLP tasks. In this paper, we propose efficient algorithms for the WordPiece tokenization used in BERT, from single-word tokenization to general text (e.g., sentence) tokenization. When tokenizing a single word, WordPiece uses a longest-match-first strategy, known as maximum matching. The best known algorithms so far are O(n^2) (where n is the input length) or O(nm) (where m is the maximum vocabulary token length). We propose a novel algorithm whose tokenization complexity is strictly O(n). Our method is inspired by the Aho-Corasick algorithm. We introduce additional linkages on top of the trie built from the vocabulary, allowing smart transitions when the trie matching cannot continue. For general text, we further propose an algorithm that combines pre-tokenization (splitting the text into words) and our linear-time WordPiece method into a single pass. Experimental results show that our method is 8.2x faster than HuggingFace Tokenizers and 5.1x faster than TensorFlow Text on average for general text tokenization.
Better Robustness by More Coverage: Adversarial Training with Mixup Augmentation for Robust Fine-tuning
Venue: arXiv cs.CL 2021
Year: 2021

Pretrained language models (PLMs) perform poorly under adversarial attacks. To improve the adversarial robustness, adversarial data augmentation (ADA) has been widely adopted to cover more search space of adversarial attacks by adding textual adversarial examples during training. However, the number of adversarial examples for text augmentation is still extremely insufficient due to the exponentially large attack search space. In this work, we propose a simple and effective method to cover a much larger proportion of the attack search space, called Adversarial and Mixup Data Augmentation (AMDA). Specifically, AMDA linearly interpolates the representations of pairs of training samples to form new virtual samples, which are more abundant and diverse than the discrete text adversarial examples in conventional ADA. Moreover, to fairly evaluate the robustness of different models, we adopt a challenging evaluation setup, which generates a new set of adversarial examples targeting each model. In text classification experiments of BERT and RoBERTa, AMDA achieves significant robustness gains under two strong adversarial attacks and alleviates the performance degradation of ADA on the clean data. Our code is available at: https://github.com/thunlp/MixADA .
Coded Machine Unlearning
Venue: arXiv cs.LG 2021
Year: 2021

There are applications that may require removing the trace of a sample from the system, e.g., a user requests their data to be deleted, or corrupted data is discovered. Simply removing a sample from storage units does not necessarily remove its entire trace since downstream machine learning models may store some information about the samples used to train them. A sample can be perfectly unlearned if we retrain all models that used it from scratch with that sample removed from their training dataset. When multiple such unlearning requests are expected to be served, unlearning by retraining becomes prohibitively expensive. Ensemble learning enables the training data to be split into smaller disjoint shards that are assigned to non-communicating weak learners. Each shard is used to produce a weak model. These models are then aggregated to produce the final central model. This setup introduces an inherent trade-off between performance and unlearning cost, as reducing the shard size reduces the unlearning cost but may cause degradation in performance. In this paper, we propose a coded learning protocol where we utilize linear encoders to encode the training data into shards prior to the learning phase. We also present the corresponding unlearning protocol and show that it satisfies the perfect unlearning criterion. Our experimental results show that the proposed coded machine unlearning provides a better performance versus unlearning cost trade-off compared to the uncoded baseline.
Scalable Graph Neural Network-based framework for identifying critical nodes and links in Complex Networks
Venue: arXiv cs.SI 2021
Year: 2021

Identifying critical nodes and links in graphs is a crucial task. These nodes/links typically represent critical elements/communication links that play a key role in a system's performance. However, a majority of the methods available in the literature on the identification of critical nodes/links are based on an iterative approach that explores each node/link of a graph at a time, repeating for all nodes/links in the graph. Such methods suffer from high computational complexity and the resulting analysis is also network-specific. To overcome these challenges, this article proposes a scalable and generic graph neural network (GNN) based framework for identifying critical nodes/links in large complex networks. The proposed framework defines a GNN based model that learns the node/link criticality score on a small representative subset of nodes/links. An appropriately trained model can be employed to predict the scores of unseen nodes/links in large graphs and consequently identify the most critical ones. The scalability of the framework is demonstrated through prediction of nodes/links scores in large scale synthetic and real-world networks. The proposed approach is fairly accurate in approximating the criticality scores and offers a significant computational advantage over conventional approaches.
Incentivizing Routing Choices for Safe and Efficient Transportation in the Face of the COVID-19 Pandemic
Venue: arXiv cs.SI 2021
Year: 2021

The COVID-19 pandemic has severely affected many aspects of people's daily lives. While many countries are in a re-opening stage, some effects of the pandemic on people's behaviors are expected to last much longer, including how they choose between different transport options. Experts predict considerably delayed recovery of the public transport options, as people try to avoid crowded places. In turn, significant increases in traffic congestion are expected, since people are likely to prefer using their own vehicles or taxis as opposed to riskier and more crowded options such as the railway. In this paper, we propose to use financial incentives to set the tradeoff between risk of infection and congestion to achieve safe and efficient transportation networks. To this end, we formulate a network optimization problem to optimize taxi fares. For our framework to be useful in various cities and times of the day without much designer effort, we also propose a data-driven approach to learn human preferences about transport options, which is then used in our taxi fare optimization. Our user studies and simulation experiments show our framework is able to minimize congestion and risk of infection.
Language-Mediated, Object-Centric Representation Learning
Venue: arXiv cs.LG 2021
Year: 2021

We present Language-mediated, Object-centric Representation Learning (LORL), a paradigm for learning disentangled, object-centric scene representations from vision and language. LORL builds upon recent advances in unsupervised object discovery and segmentation, notably MONet and Slot Attention. While these algorithms learn an object-centric representation just by reconstructing the input image, LORL enables them to further learn to associate the learned representations to concepts, i.e., words for object categories, properties, and spatial relationships, from language input. These object-centric concepts derived from language facilitate the learning of object-centric representations. LORL can be integrated with various unsupervised object discovery algorithms that are language-agnostic. Experiments show that the integration of LORL consistently improves the performance of unsupervised object discovery methods on two datasets via the help of language. We also show that concepts learned by LORL, in conjunction with object discovery methods, aid downstream tasks such as referring expression comprehension.
Semantic Modeling with SUMO
Venue: arXiv cs.AI 2021
Year: 2021

We explore using the Suggested Upper Merged Ontology (SUMO) to develop a semantic simulation. We provide two proof-of-concept demonstrations modeling transitions in a simulated gasoline engine using a general-purpose programming language. Rather than focusing on computationally highly intensive techniques, we explore a less computationally intensive approach related to familiar software engineering testing procedures. In addition, we propose structured representations of terms based on linguistic approaches to lexicography.