OpenRaiser/Intern-Atlas huggingface dataset:
Object-oriented state editing for HRL
Venue: arXiv cs.LG 2019
Year: 2019

We introduce agents that use object-oriented reasoning to consider alternate states of the world in order to more quickly find solutions to problems. Specifically, a hierarchical controller directs a low-level agent to behave as if objects in the scene were added, deleted, or modified. The actions taken by the controller are defined over a graph-based representation of the scene, with actions corresponding to adding, deleting, or editing the nodes of a graph. We present preliminary results on three environments, demonstrating that our approach can achieve similar levels of reward as non-hierarchical agents, but with better data efficiency.
Do Multi-hop Readers Dream of Reasoning Chains?
Venue: arXiv cs.CL 2019
Year: 2019

General Question Answering (QA) systems over texts require the multi-hop reasoning capability, i.e. the ability to reason with information collected from multiple passages to derive the answer. In this paper we conduct a systematic analysis to assess such an ability of various existing models proposed for multi-hop QA tasks. Specifically, our analysis investigates that whether providing the full reasoning chain of multiple passages, instead of just one final passage where the answer appears, could improve the performance of the existing QA models. Surprisingly, when using the additional evidence passages, the improvements of all the existing multi-hop reading approaches are rather limited, with the highest error reduction of 5.8% on F1 (corresponding to 1.3% absolute improvement) from the BERT model. To better understand whether the reasoning chains could indeed help find correct answers, we further develop a co-matching-based method that leads to 13.1% error reduction with passage chains when applied to two of our base readers (including BERT). Our results demonstrate the existence of the potential improvement using explicit multi-hop reasoning and the necessity to develop models with better reasoning abilities.
Visual Appearance Based Person Retrieval in Unconstrained Environment Videos
Venue: arXiv cs.CV 2019
Year: 2019

Visual appearance-based person retrieval is a challenging problem in surveillance. It uses attributes like height, cloth color, cloth type and gender to describe a human. Such attributes are known as soft biometrics. This paper proposes person retrieval from surveillance video using height, torso cloth type, torso cloth color and gender. The approach introduces an adaptive torso patch extraction and bounding box regression to improve the retrieval. The algorithm uses fine-tuned Mask R-CNN and DenseNet-169 for person detection and attribute classification respectively. The performance is analyzed on AVSS 2018 challenge II dataset and it achieves 11.35% improvement over state-of-the-art based on average Intersection over Union measure.
An Automatic Design Framework of Swarm Pattern Formation based on Multi-objective Genetic Programming
Venue: arXiv cs.NE 2019
Year: 2019

Most existing swarm pattern formation methods depend on a predefined gene regulatory network (GRN) structure that requires designers' priori knowledge, which is difficult to adapt to complex and changeable environments. To dynamically adapt to the complex and changeable environments, we propose an automatic design framework of swarm pattern formation based on multi-objective genetic programming. The proposed framework does not need to define the structure of the GRN-based model in advance, and it applies some basic network motifs to automatically structure the GRN-based model. In addition, a multi-objective genetic programming (MOGP) combines with NSGA-II, namely MOGP-NSGA-II, to balance the complexity and accuracy of the GRN-based model. In evolutionary process, an MOGP-NSGA-II and differential evolution (DE) are applied to optimize the structures and parameters of the GRN-based model in parallel. Simulation results demonstrate that the proposed framework can effectively evolve some novel GRN-based models, and these GRN-based models not only have a simpler structure and a better performance, but also are robust to the complex and changeable environments.
Modeling Feature Representations for Affective Speech using Generative Adversarial Networks
Venue: arXiv cs.LG 2019
Year: 2019

Emotion recognition is a classic field of research with a typical setup extracting features and feeding them through a classifier for prediction. On the other hand, generative models jointly capture the distributional relationship between emotions and the feature profiles. Relatively recently, Generative Adversarial Networks (GANs) have surfaced as a new class of generative models and have shown considerable success in modeling distributions in the fields of computer vision and natural language understanding. In this work, we experiment with variants of GAN architectures to generate feature vectors corresponding to an emotion in two ways: (i) A generator is trained with samples from a mixture prior. Each mixture component corresponds to an emotional class and can be sampled to generate features from the corresponding emotion. (ii) A one-hot vector corresponding to an emotion can be explicitly used to generate the features. We perform analysis on such models and also propose different metrics used to measure the performance of the GAN models in their ability to generate realistic synthetic samples. Apart from evaluation on a given dataset of interest, we perform a cross-corpus study where we study the utility of the synthetic samples as additional training data in low resource conditions.
Fog Computing for Detecting Vehicular Congestion, An Internet of Vehicles based Approach: A review
Venue: arXiv cs.NI 2019
Year: 2019

Vehicular congestion is directly impacting the efficiency of the transport sector. A wireless sensor network for vehicular clients is used in Internet of Vehicles based solutions for traffic management applications. It was found that vehicular congestion detection by using Internet of Vehicles based connected vehicles technology are practically feasible for congestion handling. It was found that by using Fog Computing based principles in the vehicular wireless sensor network, communication in the system can be improved to support larger number of nodes without impacting performance. In this paper, connected vehicles technology based vehicular congestion identification techniques are studied. Computing paradigms that can be used for the vehicular network are studied to develop a practically feasible vehicular congestion detection system that performs accurately for a large coverage area and multiple scenarios. The designed system is expected to detect congestion to meet traffic management goals that are of primary importance in intelligent transportation systems.
Explicit Programming Strategies
Venue: arXiv cs.SE 2019
Year: 2019

Software developers solve a diverse and wide range of problems. While software engineering research often focuses on tools to support this problem solving, the strategies that developers use to solve problems are at least as important. In this paper, we offer a novel approach for enabling developers to follow explicit programming strategies that describe how an expert tackles a common programming problem. We define explicit programming strategies, grounding our definition in prior work both within software engineering and in other professions which have adopted more explicit procedures for problem solving. We then present a novel notation called Roboto and a novel StrategyTracker tool that explicitly represents programming strategies and frame executing strategies as a collaborative effort between human abilities to make decisions and computer abilities to structure process and persist information. Ina formative evaluation, 28 software developers of varying expertise completed a design task and a debugging task. We found that, compared to developers who are free to choose their strategies, developers gave explicit strategies experienced their work as more organized, systematic, and predictable, but also more constrained. Developers using explicit strategies were objectively more successful at the design and debugging tasks. We discuss the implications of Roboto and these findings, envisioning a thriving ecosystem of explicit strategies that accelerate and improve developers programming problem solving.
On Neural Architecture Search for Resource-Constrained Hardware Platforms
Venue: arXiv cs.LG 2019
Year: 2019

In the recent past, the success of Neural Architecture Search (NAS) has enabled researchers to broadly explore the design space using learning-based methods. Apart from finding better neural network architectures, the idea of automation has also inspired to improve their implementations on hardware. While some practices of hardware machine-learning automation have achieved remarkable performance, the traditional design concept is still followed: a network architecture is first structured with excellent test accuracy, and then compressed and optimized to fit into a target platform. Such a design flow will easily lead to inferior local-optimal solutions. To address this problem, we propose a new framework to jointly explore the space of neural architecture, hardware implementation, and quantization. Our objective is to find a quantized architecture with the highest accuracy that is implementable on given hardware specifications. We employ FPGAs to implement and test our designs with limited loop-up tables (LUTs) and required throughput. Compared to the separate design/searching methods, our framework has demonstrated much better performance under strict specifications and generated designs of higher accuracy by 18\% to 68\% in the task of classifying CIFAR10 images. With 30,000 LUTs, a light-weight design is found to achieve 82.98\% accuracy and 1293 images/second throughput, compared to which, under the same constraints, the traditional method even fails to find a valid solution.
Dreaddit: A Reddit Dataset for Stress Analysis in Social Media
Venue: arXiv cs.CL 2019
Year: 2019

Stress is a nigh-universal human experience, particularly in the online world. While stress can be a motivator, too much stress is associated with many negative health outcomes, making its identification useful across a range of domains. However, existing computational research typically only studies stress in domains such as speech, or in short genres such as Twitter. We present Dreaddit, a new text corpus of lengthy multi-domain social media data for the identification of stress. Our dataset consists of 190K posts from five different categories of Reddit communities; we additionally label 3.5K total segments taken from 3K posts using Amazon Mechanical Turk. We present preliminary supervised learning methods for identifying stress, both neural and traditional, and analyze the complexity and diversity of the data and characteristics of each category.
AND Testing and Robust Judgement Aggregation
Venue: arXiv cs.DM 2019
Year: 2019

A function $f\colon\{0,1\}^n\to \{0,1\}$ is called an approximate AND-homomorphism if choosing ${\bf x},{\bf y}\in\{0,1\}^n$ randomly, we have that $f({\bf x}\land {\bf y}) = f({\bf x})\land f({\bf y})$ with probability at least $1-ε$, where $x\land y = (x_1\land y_1,\ldots,x_n\land y_n)$. We prove that if $f\colon \{0,1\}^n \to \{0,1\}$ is an approximate AND-homomorphism, then $f$ is $δ$-close to either a constant function or an AND function, where $δ(ε) \to 0$ as $ε\to0$. This improves on a result of Nehama, who proved a similar statement in which $δ$ depends on $n$. Our theorem implies a strong result on judgement aggregation in computational social choice. In the language of social choice, our result shows that if $f$ is $ε$-close to satisfying judgement aggregation, then it is $δ(ε)$-close to an oligarchy (the name for the AND function in social choice theory). This improves on Nehama's result, in which $δ$ decays polynomially with $n$. Our result follows from a more general one, in which we characterize approximate solutions to the eigenvalue equation $\mathrm T f = λg$, where $\mathrm T$ is the downwards noise operator $\mathrm T f(x) = \mathbb{E}_{\bf y}[f(x \land {\bf y})]$, $f$ is $[0,1]$-valued, and $g$ is $\{0,1\}$-valued. We identify all exact solutions to this equation, and show that any approximate solution in which $\mathrm T f$ and $λg$ are close is close to an exact solution.
Learning-based Real-time Detection of Intrinsic Reflectional Symmetry
Venue: arXiv cs.GR 2019
Year: 2019

Reflectional symmetry is ubiquitous in nature. While extrinsic reflectional symmetry can be easily parametrized and detected, intrinsic symmetry is much harder due to the high solution space. Previous works usually solve this problem by voting or sampling, which suffer from high computational cost and randomness. In this paper, we propose \YL{a} learning-based approach to intrinsic reflectional symmetry detection. Instead of directly finding symmetric point pairs, we parametrize this self-isometry using a functional map matrix, which can be easily computed given the signs of Laplacian eigenfunctions under the symmetric mapping. Therefore, we train a novel deep neural network to predict the sign of each eigenfunction under symmetry, which in addition takes the first few eigenfunctions as intrinsic features to characterize the mesh while avoiding coping with the connectivity explicitly. Our network aims at learning the global property of functions, and consequently converts the problem defined on the manifold to the functional domain. By disentangling the prediction of the matrix into separated basis, our method generalizes well to new shapes and is invariant under perturbation of eigenfunctions. Through extensive experiments, we demonstrate the robustness of our method in challenging cases, including different topology and incomplete shapes with holes. By avoiding random sampling, our learning-based algorithm is over 100 times faster than state-of-the-art methods, and meanwhile, is more robust, achieving higher correspondence accuracy in commonly used metrics.
Generating Justifications for Norm-Related Agent Decisions
Venue: arXiv cs.CL 2019
Year: 2019

We present an approach to generating natural language justifications of decisions derived from norm-based reasoning. Assuming an agent which maximally satisfies a set of rules specified in an object-oriented temporal logic, the user can ask factual questions (about the agent's rules, actions, and the extent to which the agent violated the rules) as well as "why" questions that require the agent comparing actual behavior to counterfactual trajectories with respect to these rules. To produce natural-sounding explanations, we focus on the subproblem of producing natural language clauses from statements in a fragment of temporal logic, and then describe how to embed these clauses into explanatory sentences. We use a human judgment evaluation on a testbed task to compare our approach to variants in terms of intelligibility, mental model and perceived trust.
Optimal Metastability-Containing Sorting via Parallel Prefix Computation
Venue: arXiv cs.DC 2019
Year: 2019

Friedrichs et al. (TC 2018) showed that metastability can be contained when sorting inputs arising from time-to-digital converters, i.e., measurement values can be correctly sorted without resolving metastability using synchronizers first. However, this work left open whether this can be done by small circuits. We show that this is indeed possible, by providing a circuit that sorts Gray code inputs (possibly containing a metastable bit) and has asymptotically optimal depth and size. Our solution utilizes the parallel prefix computation (PPC) framework (JACM 1980). We improve this construction by bounding its fan-out by an arbitrary $f \geq 3$, without affecting depth and increasing circuit size by a small constant factor only. Thus, we obtain the first PPC circuits with asymptotically optimal size, constant fan-out, and optimal depth. To show that applying the PPC framework to the sorting task is feasible, we prove that the latter can, despite potential metastability, be decomposed such that the core operation is associative. We obtain asymptotically optimal metastability-containing sorting networks. We complement these results with simulations, independently verifying the correctness as well as small size and delay of our circuits.
On the Linguistic Representational Power of Neural Machine Translation Models
Venue: arXiv cs.CL 2019
Year: 2019

Despite the recent success of deep neural networks in natural language processing (NLP), their interpretability remains a challenge. We analyze the representations learned by neural machine translation models at various levels of granularity and evaluate their quality through relevant extrinsic properties. In particular, we seek answers to the following questions: (i) How accurately is word-structure captured within the learned representations, an important aspect in translating morphologically-rich languages? (ii) Do the representations capture long-range dependencies, and effectively handle syntactically divergent languages? (iii) Do the representations capture lexical semantics? We conduct a thorough investigation along several parameters: (i) Which layers in the architecture capture each of these linguistic phenomena; (ii) How does the choice of translation unit (word, character, or subword unit) impact the linguistic properties captured by the underlying representations? (iii) Do the encoder and decoder learn differently and independently? (iv) Do the representations learned by multilingual NMT models capture the same amount of linguistic information as their bilingual counterparts? Our data-driven, quantitative evaluation illuminates important aspects in NMT models and their ability to capture various linguistic phenomena. We show that deep NMT models learn a non-trivial amount of linguistic information. Notable findings include: i) Word morphology and part-of-speech information are captured at the lower layers of the model; (ii) In contrast, lexical semantics or non-local syntactic and semantic dependencies are better represented at the higher layers; (iii) Representations learned using characters are more informed about wordmorphology compared to those learned using subword units; and (iv) Representations learned by multilingual models are richer compared to bilingual models.
Comb Convolution for Efficient Convolutional Architecture
Venue: arXiv cs.CV 2019
Year: 2019

Convolutional neural networks (CNNs) are inherently suffering from massively redundant computation (FLOPs) due to the dense connection pattern between feature maps and convolution kernels. Recent research has investigated the sparse relationship between channels, however, they ignored the spatial relationship within a channel. In this paper, we present a novel convolutional operator, namely comb convolution, to exploit the intra-channel sparse relationship among neurons. The proposed convolutional operator eliminates nearly 50% of connections by inserting uniform mappings into standard convolutions and removing about half of spatial connections in convolutional layer. Notably, our work is orthogonal and complementary to existing methods that reduce channel-wise redundancy. Thus, it has great potential to further increase efficiency through integrating the comb convolution to existing architectures. Experimental results demonstrate that by simply replacing standard convolutions with comb convolutions on state-of-the-art CNN architectures (e.g., VGGNets, Xception and SE-Net), we can achieve 50% FLOPs reduction while still maintaining the accuracy.
On the construction of multi-valued concurrent dynamic logic
Venue: arXiv cs.LO 2019
Year: 2019

Dynamic logic is a powerful framework for reasoning about imperative programs. An extension with a concurrent operator [18] was introduced to formalise programs running in parallel. In other direction, other authors proposed a systematic method for generating multi-valued propositional dynamic logics to reason about weighted programs [14]. This paper presents the first step of combining these two frameworks to introduce uncertainty in concurrent computations. In the developed framework, a weight is assigned to each branch of the parallel execution, resulting in a (possible) asymmetric parallelism, inherent to fuzzy programming paradigm [21, 2]. By adopting such an approach, a family of logics is obtained, called multi-valued concurrent propositional dynamic logics (CGDL(A)), parametric on an action lattice A specifying a notion of "weight" assigned to program execution. Additionally, the validity of some axioms of CPDL is discussed in the new family of generated logics.
Six constructions of asymptotically optimal codebooks via the character sums
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, using additive characters of finite field, we find a codebook which is equivalent to the measurement matrix in [20]. The advantage of our construction is that it can be generalized naturally to construct the other five classes of codebooks using additive and multiplicative characters of finite field. We determine the maximal cross-correlation amplitude of these codebooks by the properties of characters and character sums. We prove that all the codebooks we constructed are asymptotically optimal with respect to the Welch bound. The parameters of these codebooks are new.
MaxSAT Evaluation 2019 -- Benchmark: Identifying Security-Critical Cyber-Physical Components in Weighted AND/OR Graphs
Venue: arXiv cs.CR 2019
Year: 2019

This paper presents a MaxSAT benchmark focused on identifying critical nodes in AND/OR graphs. We use AND/OR graphs to model Industrial Control Systems (ICS) as they are able to semantically grasp intricate logical interdependencies among ICS components. However, identifying critical nodes in AND/OR graphs is an NP-complete problem. We address this problem by efficiently transforming the input AND/OR graph-based model into a weighted logical formula that is then used to build and solve a Weighted Partial MaxSAT problem. The benchmark includes 80 cases with AND/OR graphs of different size and composition as well as the optimal cost and solution for each case.
Multi-Agent Safety Verification using Symmetry Transformations
Venue: arXiv cs.FL 2019
Year: 2019

We show that symmetry transformations and caching can enable scalable, and possibly unbounded, verification of multi-agent systems. Symmetry transformations map solutions and to other solutions. We show that this property can be used to transform cached reachsets to compute new reachsets, for hybrid and multi-agent models. We develop a notion of virtual system which define symmetry transformations for a broad class of agent models that visit waypoint sequences. Using this notion of virtual system, we present a prototype tool CacheReach that builds a cache of reachtubes for this system, in a way that is agnostic of the representation of the reachsets and the reachability analysis subroutine used. Our experimental evaluation of CacheReach shows up to 66% savings in safety verification computation time on multi-agent systems with 3-dimensional linear and 4-dimensional nonlinear fixed-wing aircraft models following sequences of waypoints. These savings and our theoretical results illustrate the potential benefits of using symmetry-based caching in the safety verification of multi-agent systems.