OpenRaiser/Intern-Atlas huggingface dataset:
Approximate Bayesian Optimisation for Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

A body of work has been done to automate machine learning algorithm to highlight the importance of model choice. Automating the process of choosing the best forecasting model and its corresponding parameters can result to improve a wide range of real-world applications. Bayesian optimisation (BO) uses a blackbox optimisation methods to propose solutions according to an exploration-exploitation trade-off criterion through acquisition functions. BO framework imposes two key ingredients: a probabilistic surrogate model that consist of prior belief of the unknown objective function(data-dependant) and an objective function that describes how optimal is the model-fit. Choosing the best model and its associated hyperparameters can be very expensive, and is typically fit using Gaussian processes (GPs) and at some extends applying approximate inference due its intractability. However, since GPs scale cubically with the number of observations, it has been challenging to handle objectives whose optimization requires many evaluations. In addition, most real-dataset are non-stationary which make idealistic assumptions on surrogate models. The necessity to solve the analytical tractability and the computational feasibility in a stochastic fashion enables to ensure the efficiency and the applicability of Bayesian optimisation. In this paper we explore the use of neural networks as an alternative to GPs to model distributions over functions, we provide a link between density-ratio estimation and class probability estimation based on approximate inference, this reformulation provides algorithm efficiency and tractability.
Opinions are Made to be Changed: Temporally Adaptive Stance Classification
Venue: arXiv cs.CL 2021
Year: 2021

Given the rapidly evolving nature of social media and people's views, word usage changes over time. Consequently, the performance of a classifier trained on old textual data can drop dramatically when tested on newer data. While research in stance classification has advanced in recent years, no effort has been invested in making these classifiers have persistent performance over time. To study this phenomenon we introduce two novel large-scale, longitudinal stance datasets. We then evaluate the performance persistence of stance classifiers over time and demonstrate how it decays as the temporal gap between training and testing data increases. We propose a novel approach to mitigate this performance drop, which is based on temporal adaptation of the word embeddings used for training the stance classifier. This enables us to make use of readily available unlabelled data from the current time period instead of expensive annotation efforts. We propose and compare several approaches to embedding adaptation and find that the Incremental Temporal Alignment (ITA) model leads to the best results in reducing performance drop over time.
Positive Planar Satisfiability Problems under 3-Connectivity Constraints
Venue: arXiv cs.CC 2021
Year: 2021

A 3-SAT problem is called positive and planar if all the literals are positive and the clause-variable incidence graph (i.e., SAT graph) is planar. The NAE 3-SAT and 1-in-3-SAT are two variants of 3-SAT that remain NP-complete even when they are positive. The positive 1-in-3-SAT problem remains NP-complete under planarity constraint, but planar NAE 3-SAT is solvable in $O(n^{1.5}\log n)$ time. In this paper we prove that a positive planar NAE 3-SAT is always satisfiable when the underlying SAT graph is 3-connected, and a satisfiable assignment can be obtained in linear time. We also show that without 3-connectivity constraint, existence of a linear-time algorithm for positive planar NAE 3-SAT problem is unlikely as it would imply a linear-time algorithm for finding a spanning 2-matching in a planar subcubic graph. We then prove that positive planar 1-in-3-SAT remains NP-complete under the 3-connectivity constraint, even when each variable appears in at most 4 clauses. However, we show that the 3-connected planar 1-in-3-SAT is always satisfiable when each variable appears in an even number of clauses.
StressNAS: Affect State and Stress Detection Using Neural Architecture Search
Venue: arXiv cs.LG 2021
Year: 2021

Smartwatches have rapidly evolved towards capabilities to accurately capture physiological signals. As an appealing application, stress detection attracts many studies due to its potential benefits to human health. It is propitious to investigate the applicability of deep neural networks (DNN) to enhance human decision-making through physiological signals. However, manually engineering DNN proves a tedious task especially in stress detection due to the complex nature of this phenomenon. To this end, we propose an optimized deep neural network training scheme using neural architecture search merely using wrist-worn data from WESAD. Experiments show that our approach outperforms traditional ML methods by 8.22% and 6.02% in the three-state and two-state classifiers, respectively, using the combination of WESAD wrist signals. Moreover, the proposed method can minimize the need for human-design DNN while improving performance by 4.39% (three-state) and 8.99% (binary).
QACE: Asking Questions to Evaluate an Image Caption
Venue: arXiv cs.CL 2021
Year: 2021

In this paper, we propose QACE, a new metric based on Question Answering for Caption Evaluation. QACE generates questions on the evaluated caption and checks its content by asking the questions on either the reference caption or the source image. We first develop QACE-Ref that compares the answers of the evaluated caption to its reference, and report competitive results with the state-of-the-art metrics. To go further, we propose QACE-Img, which asks the questions directly on the image, instead of reference. A Visual-QA system is necessary for QACE-Img. Unfortunately, the standard VQA models are framed as a classification among only a few thousand categories. Instead, we propose Visual-T5, an abstractive VQA system. The resulting metric, QACE-Img is multi-modal, reference-less, and explainable. Our experiments show that QACE-Img compares favorably w.r.t. other reference-less metrics. We will release the pre-trained models to compute QACE.
A Pluralist Approach to Democratizing Online Discourse
Venue: arXiv cs.NI 2021
Year: 2021

Online discourse takes place in corporate-controlled spaces thought by users to be public realms. These platforms in name enable free speech but in practice implement varying degrees of censorship either by government edict or by uneven and unseen corporate policy. This kind of censorship has no countervailing accountability mechanism, and as such platform owners, moderators, and algorithms shape public discourse without recourse or transparency. Systems research has explored approaches to decentralizing or democratizing Internet infrastructure for decades. In parallel, the Internet censorship literature is replete with efforts to measure and overcome online censorship. However, in the course of designing specialized open-source platforms and tools, projects generally neglect the needs of supportive but uninvolved `average' users. In this paper, we propose a pluralistic approach to democratizing online discourse that considers both the systems-related and user-facing issues as first-order design goals.
Representation Memorization for Fast Learning New Knowledge without Forgetting
Venue: arXiv cs.LG 2021
Year: 2021

The ability to quickly learn new knowledge (e.g. new classes or data distributions) is a big step towards human-level intelligence. In this paper, we consider scenarios that require learning new classes or data distributions quickly and incrementally over time, as it often occurs in real-world dynamic environments. We propose "Memory-based Hebbian Parameter Adaptation" (Hebb) to tackle the two major challenges (i.e., catastrophic forgetting and sample efficiency) towards this goal in a unified framework. To mitigate catastrophic forgetting, Hebb augments a regular neural classifier with a continuously updated memory module to store representations of previous data. To improve sample efficiency, we propose a parameter adaptation method based on the well-known Hebbian theory, which directly "wires" the output network's parameters with similar representations retrieved from the memory. We empirically verify the superior performance of Hebb through extensive experiments on a wide range of learning tasks (image classification, language model) and learning scenarios (continual, incremental, online). We demonstrate that Hebb effectively mitigates catastrophic forgetting, and it indeed learns new knowledge better and faster than the current state-of-the-art.
Uncertainty-Aware Model Adaptation for Unsupervised Cross-Domain Object Detection
Venue: arXiv cs.CV 2021
Year: 2021

This work tackles the unsupervised cross-domain object detection problem which aims to generalize a pre-trained object detector to a new target domain without labels. We propose an uncertainty-aware model adaptation method, which is based on two motivations: 1) the estimation and exploitation of model uncertainty in a new domain is critical for reliable domain adaptation; and 2) the joint alignment of distributions for inputs (feature alignment) and outputs (self-training) is needed. To this end, we compose a Bayesian CNN-based framework for uncertainty estimation in object detection, and propose an algorithm for generation of uncertainty-aware pseudo-labels. We also devise a scheme for joint feature alignment and self-training of the object detection model with uncertainty-aware pseudo-labels. Experiments on multiple cross-domain object detection benchmarks show that our proposed method achieves state-of-the-art performance.
Asymptotic Frame Theory for Analog Coding
Venue: arXiv cs.IT 2021
Year: 2021

Over-complete systems of vectors, or in short, frames, play the role of analog codes in many areas of communication and signal processing. To name a few, spreading sequences for code-division multiple access (CDMA), over-complete representations for multiple-description (MD) source coding, space-time codes, sensing matrices for compressed sensing (CS), and more recently, codes for unreliable distributed computation. In this survey paper we observe an information-theoretic random-like behavior of frame subsets. Such sub-frames arise in setups involving erasures (communication), random user activity (multiple access), or sparsity (signal processing), in addition to channel or quantization noise. The goodness of a frame as an analog code is a function of the eigenvalues of a sub-frame, averaged over all sub-frames. Within the highly symmetric class of Equiangular Tight Frames (ETF), as well as other "near ETF" families, we show a universal behavior of the empirical eigenvalue distribution (ESD) of a randomly-selected sub-frame: (i) the ESD is asymptotically indistinguishable from Wachter's MANOVA distribution; and (ii) it exhibits a convergence rate to this limit that is indistinguishable from that of a matrix sequence drawn from MANOVA (Jacobi) ensembles of corresponding dimensions. Some of these results follow from careful statistical analysis of empirical evidence, and some are proved analytically using random matrix theory arguments of independent interest. The goodness measures of the MANOVA limit distribution are better, in a concrete formal sense, than those of the Marchenko-Pastur distribution at the same aspect ratio, implying that deterministic analog codes are better than random (i.i.d.) analog codes. We further give evidence that the ETF (and near ETF) family is in fact superior to any other frame family in terms of its typical sub-frame goodness.
HeadlineCause: A Dataset of News Headlines for Detecting Causalities
Venue: arXiv cs.CL 2021
Year: 2021

Detecting implicit causal relations in texts is a task that requires both common sense and world knowledge. Existing datasets are focused either on commonsense causal reasoning or explicit causal relations. In this work, we present HeadlineCause, a dataset for detecting implicit causal relations between pairs of news headlines. The dataset includes over 5000 headline pairs from English news and over 9000 headline pairs from Russian news labeled through crowdsourcing. The pairs vary from totally unrelated or belonging to the same general topic to the ones including causation and refutation relations. We also present a set of models and experiments that demonstrates the dataset validity, including a multilingual XLM-RoBERTa based model for causality detection and a GPT-2 based model for possible effects prediction.
Planar Straight-line Realizations of 2-Trees with Prescribed Edge Lengths
Venue: arXiv cs.DS 2021
Year: 2021

We study a classic problem introduced thirty years ago by Eades and Wormald. Let $G=(V,E,λ)$ be a weighted planar graph, where $λ: E \rightarrow \mathbb{R}^+$ is a length function. The Fixed Edge-Length Planar Realization problem (FEPR for short) asks whether there exists a planar straight-line realization of $G$, i.e., a planar straight-line drawing of $G$ where the Euclidean length of each edge $e \in E$ is $λ(e)$. Cabello, Demaine, and Rote showed that the FEPR problem is NP-hard, even when $λ$ assigns the same value to all the edges and the graph is triconnected. Since the existence of large triconnected minors is crucial to the known NP-hardness proofs, in this paper we investigate the computational complexity of the FEPR problem for weighted $2$-trees, which are $K_4$-minor free. We show its NP-hardness, even when $λ$ assigns to the edges only up to four distinct lengths. Conversely, we show that the FEPR problem is linear-time solvable when $λ$ assigns to the edges up to two distinct lengths, or when the input has a prescribed embedding. Furthermore, we consider the FEPR problem for weighted maximal outerplanar graphs and prove it to be linear-time solvable if their dual tree is a path, and cubic-time solvable if their dual tree is a caterpillar. Finally, we prove that the FEPR problem for weighted $2$-trees is slice-wise polynomial in the length of the longest path.
Risk-Aware Fine-Grained Access Control in Cyber-Physical Contexts
Venue: arXiv cs.CR 2021
Year: 2021

Access to resources by users may need to be granted only upon certain conditions and contexts, perhaps particularly in cyber-physical settings. Unfortunately, creating and modifying context-sensitive access control solutions in dynamic environments creates ongoing challenges to manage the authorization contexts. This paper proposes RASA, a context-sensitive access authorization approach and mechanism leveraging unsupervised machine learning to automatically infer risk-based authorization decision boundaries. We explore RASA in a healthcare usage environment, wherein cyber and physical conditions create context-specific risks for protecting private health information. The risk levels are associated with access control decisions recommended by a security policy. A coupling method is introduced to track coexistence of the objects within context using frequency and duration of coexistence, and these are clustered to reveal sets of actions with common risk levels; these are used to create authorization decision boundaries. In addition, we propose a method for assessing the risk level and labelling the clusters with respect to their corresponding risk levels. We evaluate the promise of RASA-generated policies against a heuristic rule-based policy. By employing three different coupling features (frequency-based, duration-based, and combined features), the decisions of the unsupervised method and that of the policy are more than 99% consistent.
Parameterizations of Logarithmic-Space Reductions, Stack-State Complexity of Nonuniform Families of Pushdown Automata, and a Road to the LOGCFL$\subseteq$LOGDCFL/poly Question
Venue: arXiv cs.FL 2021
Year: 2021

The complexity class LOGCFL (resp., LOGDCFL) consists of all languages that are many-one reducible to context-free (resp., deterministic context-free) languages using logarithmic space. These complexity classes have been studied over five decades in connection to parallel computation since they are located between Nick's classes $\mathrm{NC}^1$ and $\mathrm{NC}^2$. In contrast, the state complexity of nonuniform finite-automaton families was first discussed in the 1970s and it has been extensively explored lately for various finite-automata families. We extend this old subject to the stack-state complexity (i.e., the total number of inner states plus simultaneously pushable stack symbol series) of nonuniform families of various pushdown automata. We introduce reasonable "parameterizations" of LOGCFL and LOGDCFL and apply them as a technical tool to establish a close connection between the LOGCFL$\subseteq$LOGDCFL/poly question and the polynomial stack-state complexity of nonuniform families of two-way pushdown automata. We also discuss the precise computational complexity of polynomial-size one-way pushdown automata.
Attempt to Predict Failure Case Classification in a Failure Database by using Neural Network Models
Venue: arXiv cs.DC 2021
Year: 2021

With the recent progress of information technology, the use of networked information systems has rapidly expanded. Electronic commerce and electronic payments between banks and companies, and online shopping and social networking services used by the general public are examples of such systems. Therefore, in order to maintain and improve the dependability of these systems, we are constructing a failure database from past failure cases. When importing new failure cases to the database, it is necessary to classify these cases according to failure type. The problems are the accuracy and efficiency of the classification. Especially when working with multiple individuals, unification of classification is required. Therefore, we are attempting to automate classification using machine learning. As evaluation models, we selected the multilayer perceptron (MLP), the convolutional neural network (CNN), and the recurrent neural network (RNN), which are models that use neural networks. As a result, the optimal model in terms of accuracy is first the MLP followed by the CNN, and the processing time of the classification is practical.
Privacy-preserving Machine Learning for Medical Image Classification
Venue: arXiv cs.LG 2021
Year: 2021

With the rising use of Machine Learning (ML) and Deep Learning (DL) in various industries, the medical industry is also not far behind. A very simple yet extremely important use case of ML in this industry is for image classification. This is important for doctors to help them detect certain diseases timely, thereby acting as an aid to reduce chances of human judgement error. However, when using automated systems like these, there is a privacy concern as well. Attackers should not be able to get access to the medical records and images of the patients. It is also required that the model be secure, and that the data that is sent to the model and the predictions that are received both should not be revealed to the model in clear text. In this study, we aim to solve these problems in the context of a medical image classification problem of detection of pneumonia by examining chest x-ray images.
ACE: an Accurate and Cost-Effective Measurement System in SDN
Venue: arXiv cs.NI 2021
Year: 2021

Packet-level traffic measurement is essential in applications like QoS, traffic engineering, or anomaly detection. Software-Defined Networking (SDN) enables efficient and dynamic network configuration that we can deploy for fine-grained network state measurement. As the state changes dynamically, the sampling frequency must cope with that for accurate measurement. At the same time, we must consider the measurement cost, e.g., nodes' resource utilization. Existing works fall short in offering an optimal model to balance both the measurement accuracy and cost. We fill that gap by proposing ACE, an accurate and cost-effective measurement system that builds on a multi-objective optimization problem. As the optimization problem is NP-hard, we develop a heuristic. We solve the model using CPLEX; then implement a prototype of ACE in Mininet over real-world network topologies. The results confirm that ACE outperforms its counterparts in balancing both accuracy and cost.
Communication-Computation Efficient Device-Edge Co-Inference via AutoML
Venue: arXiv cs.LG 2021
Year: 2021

Device-edge co-inference, which partitions a deep neural network between a resource-constrained mobile device and an edge server, recently emerges as a promising paradigm to support intelligent mobile applications. To accelerate the inference process, on-device model sparsification and intermediate feature compression are regarded as two prominent techniques. However, as the on-device model sparsity level and intermediate feature compression ratio have direct impacts on computation workload and communication overhead respectively, and both of them affect the inference accuracy, finding the optimal values of these hyper-parameters brings a major challenge due to the large search space. In this paper, we endeavor to develop an efficient algorithm to determine these hyper-parameters. By selecting a suitable model split point and a pair of encoder/decoder for the intermediate feature vector, this problem is casted as a sequential decision problem, for which, a novel automated machine learning (AutoML) framework is proposed based on deep reinforcement learning (DRL). Experiment results on an image classification task demonstrate the effectiveness of the proposed framework in achieving a better communication-computation trade-off and significant inference speedup against various baseline schemes.
Aleatoric Description Logic for Probailistic Reasoning (Long Version)
Venue: arXiv cs.AI 2021
Year: 2021

Description logics are a powerful tool for describing ontological knowledge bases. That is, they give a factual account of the world in terms of individuals, concepts and relations. In the presence of uncertainty, such factual accounts are not feasible, and a subjective or epistemic approach is required. Aleatoric description logic models uncertainty in the world as aleatoric events, by the roll of the dice, where an agent has subjective beliefs about the bias of these dice. This provides a subjective Bayesian description logic, where propositions and relations are assigned probabilities according to what a rational agent would bet, given a configuration of possible individuals and dice. Aleatoric description logic is shown to generalise the description logic ALC, and can be seen to describe a probability space of interpretations of a restriction of ALC where all roles are functions. Several computational problems are considered and model-checking and consistency checking algorithms are presented. Finally, aleatoric description logic is shown to be able to model learning, where agents are able to condition their beliefs on the bias of dice according to observations.