OpenRaiser/Intern-Atlas huggingface dataset:
Byzantine Fault-Tolerance in Decentralized Optimization under Minimal Redundancy
Venue: arXiv cs.DC 2020
Year: 2020

This paper considers the problem of Byzantine fault-tolerance in multi-agent decentralized optimization. In this problem, each agent has a local cost function. The goal of a decentralized optimization algorithm is to allow the agents to cooperatively compute a common minimum point of their aggregate cost function. We consider the case when a certain number of agents may be Byzantine faulty. Such faulty agents may not follow a prescribed algorithm, and they may share arbitrary or incorrect information with other non-faulty agents. Presence of such Byzantine agents renders a typical decentralized optimization algorithm ineffective. We propose a decentralized optimization algorithm with provable exact fault-tolerance against a bounded number of Byzantine agents, provided the non-faulty agents have a minimal redundancy.
Approximating Nash Social Welfare under Rado Valuations
Venue: arXiv cs.GT 2020
Year: 2020

We consider the problem of approximating maximum Nash social welfare (NSW) while allocating a set of indivisible items to $n$ agents. The NSW is a popular objective that provides a balanced tradeoff between the often conflicting requirements of fairness and efficiency, defined as the weighted geometric mean of agents' valuations. For the symmetric additive case of the problem, where agents have the same weight with additive valuations, the first constant-factor approximation algorithm was obtained in 2015. This led to a flurry of work obtaining constant-factor approximation algorithms for the symmetric case under mild generalizations of additive, and $O(n)$-approximation algorithms for more general valuations and for the asymmetric case. In this paper, we make significant progress towards both symmetric and asymmetric NSW problems. We present the first constant-factor approximation algorithm for the symmetric case under Rado valuations. Rado valuations form a general class of valuation functions that arise from maximum cost independent matching problems, including as special cases assignment (OXS) valuations and weighted matroid rank functions. Furthermore, our approach also gives the first constant-factor approximation algorithm for the asymmetric case under Rado valuations, provided that the maximum ratio between the weights is bounded by a constant.
Explaining AI as an Exploratory Process: The Peircean Abduction Model
Venue: arXiv cs.AI 2020
Year: 2020

Current discussions of "Explainable AI" (XAI) do not much consider the role of abduction in explanatory reasoning (see Mueller, et al., 2018). It might be worthwhile to pursue this, to develop intelligent systems that allow for the observation and analysis of abductive reasoning and the assessment of abductive reasoning as a learnable skill. Abductive inference has been defined in many ways. For example, it has been defined as the achievement of insight. Most often abduction is taken as a single, punctuated act of syllogistic reasoning, like making a deductive or inductive inference from given premises. In contrast, the originator of the concept of abduction---the American scientist/philosopher Charles Sanders Peirce---regarded abduction as an exploratory activity. In this regard, Peirce's insights about reasoning align with conclusions from modern psychological research. Since abduction is often defined as "inferring the best explanation," the challenge of implementing abductive reasoning and the challenge of automating the explanation process are closely linked. We explore these linkages in this report. This analysis provides a theoretical framework for understanding what the XAI researchers are already doing, it explains why some XAI projects are succeeding (or might succeed), and it leads to design advice.
Creative Captioning: An AI Grand Challenge Based on the Dixit Board Game
Venue: arXiv cs.AI 2020
Year: 2020

We propose a new class of "grand challenge" AI problems that we call creative captioning---generating clever, interesting, or abstract captions for images, as well as understanding such captions. Creative captioning draws on core AI research areas of vision, natural language processing, narrative reasoning, and social reasoning, and across all these areas, it requires sophisticated uses of common sense and cultural knowledge. In this paper, we analyze several specific research problems that fall under creative captioning, using the popular board game Dixit as both inspiration and proposed testing ground. We expect that Dixit could serve as an engaging and motivating benchmark for creative captioning across numerous AI research communities for the coming 1-2 decades.
Erratum Concerning the Obfuscated Gradients Attack on Stochastic Activation Pruning
Venue: arXiv cs.LG 2020
Year: 2020

Stochastic Activation Pruning (SAP) (Dhillon et al., 2018) is a defense to adversarial examples that was attacked and found to be broken by the "Obfuscated Gradients" paper (Athalye et al., 2018). We discover a flaw in the re-implementation that artificially weakens SAP. When SAP is applied properly, the proposed attack is not effective. However, we show that a new use of the BPDA attack technique can still reduce the accuracy of SAP to 0.1%.
Interactive Re-Fitting as a Technique for Improving Word Embeddings
Venue: arXiv cs.CL 2020
Year: 2020

Word embeddings are a fixed, distributional representation of the context of words in a corpus learned from word co-occurrences. While word embeddings have proven to have many practical uses in natural language processing tasks, they reflect the attributes of the corpus upon which they are trained. Recent work has demonstrated that post-processing of word embeddings to apply information found in lexical dictionaries can improve their quality. We build on this post-processing technique by making it interactive. Our approach makes it possible for humans to adjust portions of a word embedding space by moving sets of words closer to one another. One motivating use case for this capability is to enable users to identify and reduce the presence of bias in word embeddings. Our approach allows users to trigger selective post-processing as they interact with and assess potential bias in word embeddings.
Unknown Delay for Adversarial Bandit Setting with Multiple Play
Venue: arXiv cs.LG 2020
Year: 2020

This paper addresses the problem of unknown delays in adversarial multi-armed bandit (MAB) with multiple play. Existing work on similar game setting focused on only the case where the learner selects an arm in each round. However, there are lots of applications in robotics where a learner needs to select more than one arm per round. It is therefore worthwhile to investigate the effect of delay when multiple arms are chosen. The multiple arms chosen per round in this setting are such that they experience the same amount of delay. There can be an aggregation of feedback losses from different combinations of arms selected at different rounds, and the learner is faced with the challenge of associating the feedback losses to the arms producing them. To address this problem, this paper proposes a delayed exponential, exploitation and exploration for multiple play (DEXP3.M) algorithm. The regret bound is only slightly worse than the regret of DEXP3 already proposed for the single play setting with unknown delay.
A Compare Aggregate Transformer for Understanding Document-grounded Dialogue
Venue: arXiv cs.CL 2020
Year: 2020

Unstructured documents serving as external knowledge of the dialogues help to generate more informative responses. Previous research focused on knowledge selection (KS) in the document with dialogue. However, dialogue history that is not related to the current dialogue may introduce noise in the KS processing. In this paper, we propose a Compare Aggregate Transformer (CAT) to jointly denoise the dialogue context and aggregate the document information for response generation. We designed two different comparison mechanisms to reduce noise (before and during decoding). In addition, we propose two metrics for evaluating document utilization efficiency based on word overlap. Experimental results on the CMUDoG dataset show that the proposed CAT model outperforms the state-of-the-art approach and strong baselines.
Constraint Monotonicity, Epistemic Splitting and Foundedness Could in General Be Too Strong in Answer Set Programming
Venue: arXiv cs.AI 2020
Year: 2020

Recently, the notions of subjective constraint monotonicity, epistemic splitting, and foundedness have been introduced for epistemic logic programs, with the aim to use them as main criteria respectively intuitions to compare different answer set semantics proposed in the literature on how they comply with these intuitions. In this note, we consider these three notions and demonstrate on some examples that they may be too strong in general and may exclude some desired answer sets respectively world views. In conclusion, these properties should not be regarded as mandatory properties that every answer set semantics must satisfy in general.
Quantum Annealing Approaches to the Phase-Unwrapping Problem in Synthetic-Aperture Radar Imaging
Venue: arXiv cs.CV 2020
Year: 2020

The focus of this work is to explore the use of quantum annealing solvers for the problem of phase unwrapping of synthetic aperture radar (SAR) images. Although solutions to this problem exist based on network programming, these techniques do not scale well to larger-sized images. Our approach involves formulating the problem as a quadratic unconstrained binary optimization (QUBO) problem, which can be solved using a quantum annealer. Given that present embodiments of quantum annealers remain limited in the number of qubits they possess, we decompose the problem into a set of subproblems that can be solved individually. These individual solutions are close to optimal up to an integer constant, with one constant per sub-image. In a second phase, these integer constants are determined as a solution to yet another QUBO problem. We test our approach with a variety of software-based QUBO solvers and on a variety of images, both synthetic and real. Additionally, we experiment using D-Wave Systems's quantum annealer, the D-Wave 2000Q. The software-based solvers obtain high-quality solutions comparable to state-of-the-art phase-unwrapping solvers. We are currently working on optimally mapping the problem onto the restricted topology of the quantum annealer to improve the quality of the solution.
Predicting the flow field in a U-bend with deep neural networks
Venue: arXiv cs.LG 2020
Year: 2020

This paper describes a study based on computational fluid dynamics (CFD) and deep neural networks that focusing on predicting the flow field in differently distorted U-shaped pipes. The main motivation of this work was to get an insight about the justification of the deep learning paradigm in hydrodynamic hull optimisation processes that heavily depend on computing turbulent flow fields and that could be accelerated with models like the one presented. The speed-up can be even several orders of magnitude by surrogating the CFD model with a deep convolutional neural network. An automated geometry creation and evaluation process was set up to generate differently shaped two-dimensional U-bends and to carry out CFD simulation on them. This process resulted in a database with different geometries and the corresponding flow fields (2-dimensional velocity distribution), both represented on 128x128 equidistant grids. This database was used to train an encoder-decoder style deep convolutional neural network to predict the velocity distribution from the geometry. The effect of two different representations of the geometry (binary image and signed distance function) on the predictions was examined, both models gave acceptable predictions with a speed-up of two orders of magnitude.
RefVOS: A Closer Look at Referring Expressions for Video Object Segmentation
Venue: arXiv cs.CV 2020
Year: 2020

The task of video object segmentation with referring expressions (language-guided VOS) is to, given a linguistic phrase and a video, generate binary masks for the object to which the phrase refers. Our work argues that existing benchmarks used for this task are mainly composed of trivial cases, in which referents can be identified with simple phrases. Our analysis relies on a new categorization of the phrases in the DAVIS-2017 and Actor-Action datasets into trivial and non-trivial REs, with the non-trivial REs annotated with seven RE semantic categories. We leverage this data to analyze the results of RefVOS, a novel neural network that obtains competitive results for the task of language-guided image segmentation and state of the art results for language-guided VOS. Our study indicates that the major challenges for the task are related to understanding motion and static actions.
Weighing up the new kid on the block: Impressions of using Vitis for HPC software development
Venue: arXiv cs.DC 2020
Year: 2020

The use of reconfigurable computing, and FPGAs in particular, has strong potential in the field of High Performance Computing (HPC). However the traditionally high barrier to entry when it comes to programming this technology has, until now, precluded widespread adoption. To popularise reconfigurable computing with communities such as HPC, Xilinx have recently released the first version of Vitis, a platform aimed at making the programming of FPGAs much more a question of software development rather than hardware design. However a key question is how well this technology fulfils the aim, and whether the tooling is mature enough such that software developers using FPGAs to accelerate their codes is now a more realistic proposition, or whether it simply increases the convenience for existing experts. To examine this question we use the Himeno benchmark as a vehicle for exploring the Vitis platform for building, executing and optimising HPC codes, describing the different steps and potential pitfalls of the technology. The outcome of this exploration is a demonstration that, whilst Vitis is an excellent step forwards and significantly lowers the barrier to entry in developing codes for FPGAs, it is not a silver bullet and an underlying understanding of dataflow style algorithmic design and appreciation of the architecture is still key to obtaining good performance on reconfigurable architectures.
Erratum to "Frequency Linear-time Temporal Logic"
Venue: arXiv cs.LO 2020
Year: 2020

We correct our proof of a theorem stating that satisfiability of frequency linear-time temporal logic is undecidable [TASE 2012].
On two conjectures about the intersection distribution
Venue: arXiv cs.IT 2020
Year: 2020

Recently, S. Li and A. Pott\cite{LP} proposed a new concept of intersection distribution concerning the interaction between the graph $\{(x,f(x))~|~x\in\F_{q}\}$ of $f$ and the lines in the classical affine plane $AG(2,q)$. Later, G. Kyureghyan, et al.\cite{KLP} proceeded to consider the next simplest case and derive the intersection distribution for all degree three polynomials over $\F_{q}$ with $q$ both odd and even. They also proposed several conjectures in \cite{KLP}. In this paper, we completely solve two conjectures in \cite{KLP}. Namely, we prove two classes of power functions having intersection distribution: $v_{0}(f)=\frac{q(q-1)}{3},~v_{1}(f)=\frac{q(q+1)}{2},~v_{2}(f)=0,~v_{3}(f)=\frac{q(q-1)}{6}$. We mainly make use of the multivariate method and QM-equivalence on $2$-to-$1$ mappings. The key point of our proof is to consider the number of the solutions of some low-degree equations.
Detecting White Supremacist Hate Speech using Domain Specific Word Embedding with Deep Learning and BERT
Venue: arXiv cs.CL 2020
Year: 2020

White supremacists embrace a radical ideology that considers white people superior to people of other races. The critical influence of these groups is no longer limited to social media; they also have a significant effect on society in many ways by promoting racial hatred and violence. White supremacist hate speech is one of the most recently observed harmful content on social media.Traditional channels of reporting hate speech have proved inadequate due to the tremendous explosion of information, and therefore, it is necessary to find an automatic way to detect such speech in a timely manner. This research investigates the viability of automatically detecting white supremacist hate speech on Twitter by using deep learning and natural language processing techniques. Through our experiments, we used two approaches, the first approach is by using domain-specific embeddings which are extracted from white supremacist corpus in order to catch the meaning of this white supremacist slang with bidirectional Long Short-Term Memory (LSTM) deep learning model, this approach reached a 0.74890 F1-score. The second approach is by using the one of the most recent language model which is BERT, BERT model provides the state of the art of most NLP tasks. It reached to a 0.79605 F1-score. Both approaches are tested on a balanced dataset given that our experiments were based on textual data only. The dataset was combined from dataset created from Twitter and a Stormfront dataset compiled from that white supremacist forum.
Quasar Detection using Linear Support Vector Machine with Learning From Mistakes Methodology
Venue: arXiv cs.LG 2020
Year: 2020

The field of Astronomy requires the collection and assimilation of vast volumes of data. The data handling and processing problem has become severe as the sheer volume of data produced by scientific instruments each night grows exponentially. This problem becomes extensive for conventional methods of processing the data, which was mostly manual, but is the perfect setting for the use of Machine Learning approaches. While building classifiers for Astronomy, the cost of losing a rare object like supernovae or quasars to detection losses is far more severe than having many false positives, given the rarity and scientific value of these objects. In this paper, a Linear Support Vector Machine (LSVM) is explored to detect Quasars, which are extremely bright objects in which a supermassive black hole is surrounded by a luminous accretion disk. In Astronomy, it is vital to correctly identify quasars, as they are very rare in nature. Their rarity creates a class-imbalance problem that needs to be taken into consideration. The class-imbalance problem and high cost of misclassification are taken into account while designing the classifier. To achieve this detection, a novel classifier is explored, and its performance is evaluated. It was observed that LSVM along with Ensemble Bagged Trees (EBT) achieved a 10x reduction in the False Negative Rate, using the Learning from Mistakes methodology.
Meta-Heuristic Solutions to a Student Grouping Optimization Problem faced in Higher Education Institutions
Venue: arXiv cs.AI 2020
Year: 2020

Combinatorial problems which have been proven to be NP-hard are faced in Higher Education Institutions and researches have extensively investigated some of the well-known combinatorial problems such as the timetabling and student project allocation problems. However, NP-hard problems faced in Higher Education Institutions are not only confined to these categories of combinatorial problems. The majority of NP-hard problems faced in institutions involve grouping students and/or resources, albeit with each problem having its own unique set of constraints. Thus, it can be argued that techniques to solve NP-hard problems in Higher Education Institutions can be transferred across the different problem categories. As no method is guaranteed to outperform all others in all problems, it is necessary to investigate heuristic techniques for solving lesser-known problems in order to guide stakeholders or software developers to the most appropriate algorithm for each unique class of NP-hard problems faced in Higher Education Institutions. To this end, this study described an optimization problem faced in a real university that involved grouping students for the presentation of semester results. Ordering based heuristics, genetic algorithm and the ant colony optimization algorithm implemented in Python programming language were used to find feasible solutions to this problem, with the ant colony optimization algorithm performing better or equal in 75% of the test instances and the genetic algorithm producing better or equal results in 38% of the test instances.
PipeTune: Pipeline Parallelism of Hyper and System Parameters Tuning for Deep Learning Clusters
Venue: arXiv cs.DC 2020
Year: 2020

DNN learning jobs are common in today's clusters due to the advances in AI driven services such as machine translation and image recognition. The most critical phase of these jobs for model performance and learning cost is the tuning of hyperparameters. Existing approaches make use of techniques such as early stopping criteria to reduce the tuning impact on learning cost. However, these strategies do not consider the impact that certain hyperparameters and systems parameters have on training time. This paper presents PipeTune, a framework for DNN learning jobs that addresses the trade-offs between these two types of parameters. PipeTune takes advantage of the high parallelism and recurring characteristics of such jobs to minimize the learning cost via a pipelined simultaneous tuning of both hyper and system parameters. Our experimental evaluation using three different types of workloads indicates that PipeTune achieves up to 22.6% reduction and 1.7x speed up on tuning and training time, respectively. PipeTune not only improves performance but also lowers energy consumption up to 29%.
Why Adversarial Interaction Creates Non-Homogeneous Patterns: A Pseudo-Reaction-Diffusion Model for Turing Instability
Venue: arXiv cs.LG 2020
Year: 2020

Long after Turing's seminal Reaction-Diffusion (RD) model, the elegance of his fundamental equations alleviated much of the skepticism surrounding pattern formation. Though Turing model is a simplification and an idealization, it is one of the best-known theoretical models to explain patterns as a reminiscent of those observed in nature. Over the years, concerted efforts have been made to align theoretical models to explain patterns in real systems. The apparent difficulty in identifying the specific dynamics of the RD system makes the problem particularly challenging. Interestingly, we observe Turing-like patterns in a system of neurons with adversarial interaction. In this study, we establish the involvement of Turing instability to create such patterns. By theoretical and empirical studies, we present a pseudo-reaction-diffusion model to explain the mechanism that may underlie these phenomena. While supervised learning attains homogeneous equilibrium, this paper suggests that the introduction of an adversary helps break this homogeneity to create non-homogeneous patterns at equilibrium. Further, we prove that randomly initialized gradient descent with over-parameterization can converge exponentially fast to an $ε$-stationary point even under adversarial interaction. In addition, different from sole supervision, we show that the solutions obtained under adversarial interaction are not limited to a tiny subspace around initialization.