OpenRaiser/Intern-Atlas huggingface dataset:
Summer Research Report: Towards Incremental Lazard Cylindrical Algebraic Decomposition
Venue: arXiv cs.SC 2018
Year: 2018

Cylindrical Algebraic Decomposition (CAD) is an important tool within computational real algebraic geometry, capable of solving many problems to do with polynomial systems over the reals, but known to have worst-case computational complexity doubly exponential in the number of variables. It has long been studied by the Symbolic Computation community and is implemented in a variety of computer algebra systems, however, it has also found recent interest in the Satisfiability Checking community for use with SMT-solvers. The SCSC Project seeks to build bridges between these communities. The present report describes progress made during a Research Internship in Summer 2017 funded by the EU H2020 SCSC CSA. We describe a proof of concept implementation of an Incremental CAD algorithm in Maple, where CADs are built and refined incrementally by polynomial constraint, in contrast to the usual approach of a single computation from a single input. This advance would make CAD of use to SMT-solvers who search for solutions by constantly reformulating logical formula and querying solvers like CAD for whether a logical solution is admissible. We describe experiments for the proof of concept, which clearly display the computational advantages when compared to iterated re-computation. In addition, the project implemented this work under the recently verified Lazard projection scheme (with corresponding Lazard evaluation). That is the minimal complete CAD method in theory, and this is the first documented implementation.
Towards Symbolic Reinforcement Learning with Common Sense
Venue: arXiv cs.LG 2018
Year: 2018

Deep Reinforcement Learning (deep RL) has made several breakthroughs in recent years in applications ranging from complex control tasks in unmanned vehicles to game playing. Despite their success, deep RL still lacks several important capacities of human intelligence, such as transfer learning, abstraction and interpretability. Deep Symbolic Reinforcement Learning (DSRL) seeks to incorporate such capacities to deep Q-networks (DQN) by learning a relevant symbolic representation prior to using Q-learning. In this paper, we propose a novel extension of DSRL, which we call Symbolic Reinforcement Learning with Common Sense (SRL+CS), offering a better balance between generalization and specialization, inspired by principles of common sense when assigning rewards and aggregating Q-values. Experiments reported in this paper show that SRL+CS learns consistently faster than Q-learning and DSRL, achieving also a higher accuracy. In the hardest case, where agents were trained in a deterministic environment and tested in a random environment, SRL+CS achieves nearly 100% average accuracy compared to DSRL's 70% and DQN's 50% accuracy. To the best of our knowledge, this is the first case of near perfect zero-shot transfer learning using Reinforcement Learning.
Faster Response in Bounded-Update-Rate, Discrete-time Networks using Delayed Self-Reinforcement
Venue: arXiv cs.SY 2018
Year: 2018

The response speed of a network impacts the efficacy of its actions to external stimuli. However, for a given bound on the update rate, the network-response speed is limited by the need to maintain stability. This work increases the network-response speed without having to increase the update rate by using delayed self-reinforcement (DSR), where each agent uses its already available information from the network to strengthen its individual update law. Example simulation results are presented that show more than an order of magnitude improvement in the response speed (quantified using the settling time) with the proposed DSR approach.
Parameter Transfer Unit for Deep Neural Networks
Venue: arXiv cs.LG 2018
Year: 2018

Parameters in deep neural networks which are trained on large-scale databases can generalize across multiple domains, which is referred as "transferability". Unfortunately, the transferability is usually defined as discrete states and it differs with domains and network architectures. Existing works usually heuristically apply parameter-sharing or fine-tuning, and there is no principled approach to learn a parameter transfer strategy. To address the gap, a parameter transfer unit (PTU) is proposed in this paper. The PTU learns a fine-grained nonlinear combination of activations from both the source and the target domain networks, and subsumes hand-crafted discrete transfer states. In the PTU, the transferability is controlled by two gates which are artificial neurons and can be learned from data. The PTU is a general and flexible module which can be used in both CNNs and RNNs. Experiments are conducted with various network architectures and multiple transfer domain pairs. Results demonstrate the effectiveness of the PTU as it outperforms heuristic parameter-sharing and fine-tuning in most settings.
State Distribution-aware Sampling for Deep Q-learning
Venue: arXiv cs.LG 2018
Year: 2018

A critical and challenging problem in reinforcement learning is how to learn the state-action value function from the experience replay buffer and simultaneously keep sample efficiency and faster convergence to a high quality solution. In prior works, transitions are uniformly sampled at random from the replay buffer or sampled based on their priority measured by temporal-difference (TD) error. However, these approaches do not fully take into consideration the intrinsic characteristics of transition distribution in the state space and could result in redundant and unnecessary TD updates, slowing down the convergence of the learning procedure. To overcome this problem, we propose a novel state distribution-aware sampling method to balance the replay times for transitions with skew distribution, which takes into account both the occurrence frequencies of transitions and the uncertainty of state-action values. Consequently, our approach could reduce the unnecessary TD updates and increase the TD updates for state-action value with more uncertainty, making the experience replay more effective and efficient. Extensive experiments are conducted on both classic control tasks and Atari 2600 games based on OpenAI gym platform and the experimental results demonstrate the effectiveness of our approach in comparison with the standard DQN approach.
Unmanned Aerial Vehicle Forensic Investigation Process: Dji Phantom 3 Drone As A Case Study
Venue: arXiv cs.CR 2018
Year: 2018

Drones (also known as Unmanned Aerial Vehicles, UAVs) is a potential source of evidence in a digital investigation, partly due to their increasing popularity in our society. However, existing UAV/drone forensics generally rely on conventional digital forensic investigation guidelines such as those of ACPO and NIST, which may not be entirely fit_for_purpose. In this paper, we identify the challenges associated with UAV/drone forensics. We then explore and evaluate existing forensic guidelines, in terms of their effectiveness for UAV/drone forensic investigations. Next, we present our set of guidelines for UAV/drone investigations. Finally, we demonstrate how the proposed guidelines can be used to guide a drone forensic investigation using the DJI Phantom 3 drone as a case study.
Rendition: Reclaiming what a black box takes away
Venue: arXiv cs.CV 2018
Year: 2018

The premise of our work is deceptively familiar: A black box $f(\cdot)$ has altered an image $\mathbf{x} \rightarrow f(\mathbf{x})$. Recover the image $\mathbf{x}$. This black box might be any number of simple or complicated things: a linear or non-linear filter, some app on your phone, etc. The latter is a good canonical example for the problem we address: Given only "the app" and an image produced by the app, find the image that was fed to the app. You can run the given image (or any other image) through the app as many times as you like, but you can not look inside the (code for the) app to see how it works. At first blush, the problem sounds a lot like a standard inverse problem, but it is not in the following sense: While we have access to the black box $f(\cdot)$ and can run any image through it and observe the output, we do not know how the block box alters the image. Therefore we have no explicit form or model of $f(\cdot)$. Nor are we necessarily interested in the internal workings of the black box. We are simply happy to reverse its effect on a particular image, to whatever extent possible. This is what we call the "rendition" (rather than restoration) problem, as it does not fit the mold of an inverse problem (blind or otherwise). We describe general conditions under which rendition is possible, and provide a remarkably simple algorithm that works for both contractive and expansive black box operators. The principal and novel take-away message from our work is this surprising fact: One simple algorithm can reliably undo a wide class of (not too violent) image distortions. A higher quality pdf of this paper is available at http://www.milanfar.org
Influencing Flock Formation in Low-Density Settings
Venue: arXiv cs.MA 2018
Year: 2018

Flocking is a coordinated collective behavior that results from local sensing between individual agents that have a tendency to orient towards each other. Flocking is common among animal groups and might also be useful in robotic swarms. In the interest of learning how to control flocking behavior, recent work in the multiagent systems literature has explored the use of influencing agents for guiding flocking agents to face a target direction. The existing work in this domain has focused on simulation settings of small areas with toroidal shapes. In such settings, agent density is high, so interactions are common, and flock formation occurs easily. In our work, we study new environments with lower agent density, wherein interactions are more rare. We study the efficacy of placement strategies and influencing agent behaviors drawn from the literature, and find that the behaviors that have been shown to work well in high-density conditions tend to be much less effective in lower density environments. The source of this ineffectiveness is that the influencing agents explored in prior work tended to face directions optimized for maximal influence, but which actually separate the influencing agents from the flock. We find that in low-density conditions maintaining a connection to the flock is more important than rushing to orient towards the desired direction. We use these insights to propose new influencing agent behaviors, which we dub "follow-then-influence"; agents act like normal members of the flock to achieve positions that allow for control and then exert their influence. This strategy overcomes the difficulties posed by low density environments.
StreamBED: Training Citizen Scientists to Make Qualitative Judgments Using Embodied Virtual Reality Training
Venue: arXiv cs.HC 2018
Year: 2018

Environmental citizen science frequently relies on experience-based assessment, however volunteers are not trained to make qualitative judgments. Embodied learning in virtual reality (VR) has been explored as a way to train behavior, but has not fully been considered as a way to train judgment. This preliminary research explores embodied learning in VR through the design, evaluation, and redesign of StreamBED, a water quality monitoring training environment that teaches volunteers to make qualitative assessments by exploring, assessing and comparing virtual watersheds.
Detecting Syntactic Features of Translated Chinese
Venue: arXiv cs.CL 2018
Year: 2018

We present a machine learning approach to distinguish texts translated to Chinese (by humans) from texts originally written in Chinese, with a focus on a wide range of syntactic features. Using Support Vector Machines (SVMs) as classifier on a genre-balanced corpus in translation studies of Chinese, we find that constituent parse trees and dependency triples as features without lexical information perform very well on the task, with an F-measure above 90%, close to the results of lexical n-gram features, without the risk of learning topic information rather than translation features. Thus, we claim syntactic features alone can accurately distinguish translated from original Chinese. Translated Chinese exhibits an increased use of determiners, subject position pronouns, NP + 'de' as NP modifiers, multiple NPs or VPs conjoined by a Chinese specific punctuation, among other structures. We also interpret the syntactic features with reference to previous translation studies in Chinese, particularly the usage of pronouns.
Neural-Brane: Neural Bayesian Personalized Ranking for Attributed Network Embedding
Venue: arXiv cs.LG 2018
Year: 2018

Network embedding methodologies, which learn a distributed vector representation for each vertex in a network, have attracted considerable interest in recent years. Existing works have demonstrated that vertex representation learned through an embedding method provides superior performance in many real-world applications, such as node classification, link prediction, and community detection. However, most of the existing methods for network embedding only utilize topological information of a vertex, ignoring a rich set of nodal attributes (such as, user profiles of an online social network, or textual contents of a citation network), which is abundant in all real-life networks. A joint network embedding that takes into account both attributional and relational information entails a complete network information and could further enrich the learned vector representations. In this work, we present Neural-Brane, a novel Neural Bayesian Personalized Ranking based Attributed Network Embedding. For a given network, Neural-Brane extracts latent feature representation of its vertices using a designed neural network model that unifies network topological information and nodal attributes; Besides, it utilizes Bayesian personalized ranking objective, which exploits the proximity ordering between a similar node-pair and a dissimilar node-pair. We evaluate the quality of vertex embedding produced by Neural-Brane by solving the node classification and clustering tasks on four real-world datasets. Experimental results demonstrate the superiority of our proposed method over the state-of-the-art existing methods.
A Tight 4/3 Approximation for Capacitated Vehicle Routing in Trees
Venue: arXiv cs.DS 2018
Year: 2018

Given a set of clients with demands, the Capacitated Vehicle Routing problem is to find a set of tours that collectively cover all client demand, such that the capacity of each vehicle is not exceeded and such that the sum of the tour lengths is minimized. In this paper, we provide a 4/3-approximation algorithm for Capacitated Vehicle Routing on trees, improving over the previous best-known approximation ratio of $(\sqrt{41}-1)/4$ by Asano et al., while using the same lower bound. Asano et al. show that there exist instances whose optimal cost is 4/3 times this lower bound. Notably, our 4/3 approximation ratio is therefore tight for this lower bound, achieving the best-possible performance.
In-Browser Split-Execution Support for Interactive Analytics in the Cloud
Venue: arXiv cs.DB 2018
Year: 2018

The canonical analytics architecture today consists of a browser connected to a backend in the cloud. In all deployments that we are aware of, the browser is simply a dumb rendering endpoint. As an alternative, this paper explores split-execution architectures that push analytics capabilities into the browser. We show that, by taking advantage of typed arrays and asm.js, it is possible to build an analytical RDBMS in JavaScript that runs in a browser, achieving performance rivaling native databases. To support interactive data exploration, our Afterburner prototype automatically generates local materialized views from a backend database that are then shipped to the browser to facilitate subsequent interactions seamlessly and efficiently. We compare this architecture to several alternative deployments, experimentally demonstrating performance parity, while at the same time providing additional advantages in terms of administrative and operational simplicity.
Assessment of Deep Convolutional Neural Networks for Road Surface Classification
Venue: arXiv cs.CV 2018
Year: 2018

When parameterizing vehicle control algorithms for stability or trajectory control, the road-tire friction coefficient is an essential model parameter when it comes to control performance. One major impact on the friction coefficient is the condition of the road surface. A camera-based, forward-looking classification of the road-surface helps enabling an early parametrization of vehicle control algorithms. In this paper, we train and compare two different Deep Convolutional Neural Network models, regarding their application for road friction estimation and describe the challenges for training the classifier in terms of available training data and the construction of suitable datasets.
A multi-level collaborative filtering method that improves recommendations
Venue: arXiv cs.IR 2018
Year: 2018

Collaborative filtering is one of the most used approaches for providing recommendations in various online environments. Even though collaborative recommendation methods have been widely utilized due to their simplicity and ease of use, accuracy is still an issue. In this paper we propose a multi-level recommendation method with its main purpose being to assist users in decision making by providing recommendations of better quality. The proposed method can be applied in different online domains that use collaborative recommender systems, thus improving the overall user experience. The efficiency of the proposed method is shown by providing an extensive experimental evaluation using five real datasets and with comparisons to alternatives.
Learning-Based Mean-Payoff Optimization in an Unknown MDP under Omega-Regular Constraints
Venue: arXiv cs.AI 2018
Year: 2018

We formalize the problem of maximizing the mean-payoff value with high probability while satisfying a parity objective in a Markov decision process (MDP) with unknown probabilistic transition function and unknown reward function. Assuming the support of the unknown transition function and a lower bound on the minimal transition probability are known in advance, we show that in MDPs consisting of a single end component, two combinations of guarantees on the parity and mean-payoff objectives can be achieved depending on how much memory one is willing to use. (i) For all $ε$ and $γ$ we can construct an online-learning finite-memory strategy that almost-surely satisfies the parity objective and which achieves an $ε$-optimal mean payoff with probability at least $1 - γ$. (ii) Alternatively, for all $ε$ and $γ$ there exists an online-learning infinite-memory strategy that satisfies the parity objective surely and which achieves an $ε$-optimal mean payoff with probability at least $1 - γ$. We extend the above results to MDPs consisting of more than one end component in a natural way. Finally, we show that the aforementioned guarantees are tight, i.e. there are MDPs for which stronger combinations of the guarantees cannot be ensured.
Efficient Equalization Method for Cyclic Prefix-Free Coarsely Quantized Massive MIMO Systems
Venue: arXiv cs.IT 2018
Year: 2018

The use of low resolution Analog to Digital Converters (ADCs) can significantly reduce the power consumption for massive Multiple Input Multiple Output (MIMO) systems. The existing literature on quantized massive MIMO systems deals with Cyclic Prefix (CP) transmission schemes in frequency-selective fading channels. In this paper, we propose a block processing Frequency Domain Equalization (FDE) technique in CP-free transmission schemes for massive MIMO systems having low resolution ADCs. The optimal block length for FDE is found by minimizing a computational complexity cost function and taking quantization distortion, channel impulse response and the number of transmit and receiver antennas into account. Through numerical simulation, it is shown that the optimal block length also guarantees good performance in terms of the Mean Square Error (MSE) and Bit Error-Rate (BER) criterion.
An Algorithm for Generating Strongly Chordal Graphs
Venue: arXiv cs.DS 2018
Year: 2018

Strongly chordal graphs are a subclass of chordal graphs. The interest in this subclass stems from the fact that many problems which are NP-complete for chordal graphs are solvable in polynomial time for this subclass. However, we are not aware of any algorithm that can generate instances of this class, often necessary for testing purposes. In this paper, we address this issue. Our algorithm first generates chordal graphs, using an available algorithm and then adds enough edges to make it strongly chordal, unless it is already so. The edge additions are based on a totally balanced matrix characterizations of strongly chordal graphs.
International Research Collaboration: Novelty, Conventionality, and Atypicality in Knowledge Recombination
Venue: arXiv cs.SI 2018
Year: 2018

Research articles produced through international collaboration are more highly cited than other work, but are they also more novel? Using measures developed by Uzzi et al. (2013), and replicated by Boyack and Klavans (2014), this article tests for novelty and conventionality in international research collaboration. Scholars have found that coauthored articles are more novel and have suggested that diverse groups have a greater chance of producing creative work. As such, we expected to find that international collaboration tends to produce more novel research. Using data from Web of Science and Scopus in 2005, we failed to show that international collaboration tends to produce more novel articles. In fact, international collaboration appears to produce less novel and more conventional knowledge combinations. Transaction costs and communication barriers to international collaboration may suppress novelty. Higher citations to international work may be explained by an audience effect, where more authors from more countries results in greater access to a larger citing community. The findings are consistent with explanations of growth in international collaboration that posit a social dynamic of preferential attachment based upon reputation.
Semi-supervised Content-based Detection of Misinformation via Tensor Embeddings
Venue: arXiv cs.LG 2018
Year: 2018

Fake news may be intentionally created to promote economic, political and social interests, and can lead to negative impacts on humans beliefs and decisions. Hence, detection of fake news is an emerging problem that has become extremely prevalent during the last few years. Most existing works on this topic focus on manual feature extraction and supervised classification models leveraging a large number of labeled (fake or real) articles. In contrast, we focus on content-based detection of fake news articles, while assuming that we have a small amount of labels, made available by manual fact-checkers or automated sources. We argue this is a more realistic setting in the presence of massive amounts of content, most of which cannot be easily factchecked. To that end, we represent collections of news articles as multi-dimensional tensors, leverage tensor decomposition to derive concise article embeddings that capture spatial/contextual information about each news article, and use those embeddings to create an article-by-article graph on which we propagate limited labels. Results on three real-world datasets show that our method performs on par or better than existing models that are fully supervised, in that we achieve better detection accuracy using fewer labels. In particular, our proposed method achieves 75.43% of accuracy using only 30% of labels of a public dataset while an SVM-based classifier achieved 67.43%. Furthermore, our method achieves 70.92% of accuracy in a large dataset using only 2% of labels.