OpenRaiser/Intern-Atlas huggingface dataset:
Characterizing Political Fake News in Twitter by its Meta-Data
Venue: arXiv cs.CL 2017
Year: 2017

This article presents a preliminary approach towards characterizing political fake news on Twitter through the analysis of their meta-data. In particular, we focus on more than 1.5M tweets collected on the day of the election of Donald Trump as 45th president of the United States of America. We use the meta-data embedded within those tweets in order to look for differences between tweets containing fake news and tweets not containing them. Specifically, we perform our analysis only on tweets that went viral, by studying proxies for users' exposure to the tweets, by characterizing accounts spreading fake news, and by looking at their polarization. We found significant differences on the distribution of followers, the number of URLs on tweets, and the verification of the users.
Study on the Best Uses of Technology in Support of Project-Based Learning
Venue: arXiv cs.CY 2017
Year: 2017

Project-Based Learning (PBL) is a teaching technique in which authentic, real-world projects are used as the primary vehicle to drive the student's learning experience. This technique has been found to be very effective, but its overall adoption rate is relatively low, in part due to teachers' unfamiliarity with how to best use technology to successfully implement it. This research study involved a comprehensive survey of supportive technology tools, as well as secondary survey research from students and teachers with actual experience in PBL. The goal was to determine which types of technology tools were most supportive of PBL. Overall, the study found that teachers and students are mostly aligned with regards to the importance of technology and the effectiveness of various types of tools. Tools which fostered collaboration amongst teacher and students were ultimately deemed the most effective, but content-development and assessment tools were also found to be particularly helpful.
Towards a science of human stories: using sentiment analysis and emotional arcs to understand the building blocks of complex social systems
Venue: arXiv cs.CL 2017
Year: 2017

Given the growing assortment of sentiment measuring instruments, it is imperative to understand which aspects of sentiment dictionaries contribute to both their classification accuracy and their ability to provide richer understanding of texts. Here, we perform detailed, quantitative tests and qualitative assessments of 6 dictionary-based methods applied, and briefly examine a further 20 methods. We show that while inappropriate for sentences, dictionary-based methods are generally robust in their classification accuracy for longer texts. Stories often following distinct emotional trajectories, forming patterns that are meaningful to us. By classifying the emotional arcs for a filtered subset of 4,803 stories from Project Gutenberg's fiction collection, we find a set of six core trajectories which form the building blocks of complex narratives. Of profound scientific interest will be the degree to which we can eventually understand the full landscape of human stories, and data driven approaches will play a crucial role. Finally, we utilize web-scale data from Twitter to study the limits of what social data can tell us about public health, mental illness, discourse around the protest movement of #BlackLivesMatter, discourse around climate change, and hidden networks. We conclude with a review of published works in complex systems that separately analyze charitable donations, the happiness of words in 10 languages, 100 years of daily temperature data across the United States, and Australian Rules Football games.
Incentive Mechanism Design for Wireless Energy Harvesting-Based Internet of Things
Venue: arXiv cs.IT 2017
Year: 2017

Radio frequency energy harvesting (RFEH) is a promising technology to charge unattended Internet of Things (IoT) low-power devices remotely. To enable this, in future IoT system, besides the traditional data access points (DAPs) for collecting data, energy access points (EAPs) should be deployed to charge IoT devices to maintain their sustainable operations. Practically, the DAPs and EAPs may be operated by different operators, and the DAPs thus need to provide effective incentives to motivate the surrounding EAPs to charge their associated IoT devices. Different from existing incentive schemes, we consider a practical scenario with asymmetric information, where the DAP is not aware of the channel conditions and energy costs of the EAPs. We first extend the existing Stackelberg game-based approach with complete information to the asymmetric information scenario, where the expected utility of the DAP is defined and maximized. To deal with asymmetric information more efficiently, we then develop a contract theory-based framework, where the optimal contract is derived to maximize the DAP's expected utility as well as the social welfare. Simulations show that information asymmetry leads to severe performance degradation for the Stackelberg game-based framework, while the proposed contract theory-based approach using asymmetric information outperforms the Stackelberg game-based method with complete information. This reveals that the performance of the considered system depends largely on the market structure (i.e., whether the EAPs are allowed to optimize their received power at the IoT devices with full freedom or not) than on the information availability (i.e., the complete or asymmetric information).
Low Resourced Machine Translation via Morpho-syntactic Modeling: The Case of Dialectal Arabic
Venue: arXiv cs.CL 2017
Year: 2017

We present the second ever evaluated Arabic dialect-to-dialect machine translation effort, and the first to leverage external resources beyond a small parallel corpus. The subject has not previously received serious attention due to lack of naturally occurring parallel data; yet its importance is evidenced by dialectal Arabic's wide usage and breadth of inter-dialect variation, comparable to that of Romance languages. Our results suggest that modeling morphology and syntax significantly improves dialect-to-dialect translation, though optimizing such data-sparse models requires consideration of the linguistic differences between dialects and the nature of available data and resources. On a single-reference blind test set where untranslated input scores 6.5 BLEU and a model trained only on parallel data reaches 14.6, pivot techniques and morphosyntactic modeling significantly improve performance to 17.5.
Bounding Errors Due to Switching Delays in Incrementally Stable Switched Systems (Extended Version)
Venue: arXiv cs.SY 2017
Year: 2017

Time delays pose an important challenge in networked control systems, which are now ubiquitous. Focusing on switched systems, we introduce a framework that provides an upper bound for errors caused by switching delays. Our framework is based on approximate bisimulation, a notion that has been previously utilized mainly for symbolic (discrete) abstraction of state spaces. Notable in our framework is that, in deriving an approximate bisimulation and thus an error bound, we use a simple incremental stability assumption (namely δ-GUAS) that does not itself refer to time delays. That this is the same assumption used for state-space discretization enables a two-step workflow for control synthesis for switched systems, in which a single Lyapunov-type stability witness serves for two different purposes of state discretization and coping with time delays. We demonstrate the proposed framework with a boost DC-DC converter, a common example of switched systems.
A Shapelet Transform for Multivariate Time Series Classification
Venue: arXiv cs.LG 2017
Year: 2017

Shapelets are phase independent subsequences designed for time series classification. We propose three adaptations to the Shapelet Transform (ST) to capture multivariate features in multivariate time series classification. We create a unified set of data to benchmark our work on, and compare with three other algorithms. We demonstrate that multivariate shapelets are not significantly worse than other state-of-the-art algorithms.
Different approaches to community detection
Venue: arXiv cs.SI 2017
Year: 2017

A precise definition of what constitutes a community in networks has remained elusive. Consequently, network scientists have compared community detection algorithms on benchmark networks with a particular form of community structure and classified them based on the mathematical techniques they employ. However, this comparison can be misleading because apparent similarities in their mathematical machinery can disguise different reasons for why we would want to employ community detection in the first place. Here we provide a focused review of these different motivations that underpin community detection. This problem-driven classification is useful in applied network science, where it is important to select an appropriate algorithm for the given purpose. Moreover, highlighting the different approaches to community detection also delineates the many lines of research and points out open directions and avenues for future research.
The Power of Vertex Sparsifiers in Dynamic Graph Algorithms
Venue: arXiv cs.DS 2017
Year: 2017

We introduce a new algorithmic framework for designing dynamic graph algorithms in minor-free graphs, by exploiting the structure of such graphs and a tool called vertex sparsification, which is a way to compress large graphs into small ones that well preserve relevant properties among a subset of vertices and has previously mainly been used in the design of approximation algorithms. Using this framework, we obtain a Monte Carlo randomized fully dynamic algorithm for $(1+\varepsilon)$-approximating the energy of electrical flows in $n$-vertex planar graphs with $\tilde{O}(r\varepsilon^{-2})$ worst-case update time and $\tilde{O}((r+\frac{n}{\sqrt{r}})\varepsilon^{-2})$ worst-case query time, for any $r$ larger than some constant. For $r=n^{2/3}$, this gives $\tilde{O}(n^{2/3}\varepsilon^{-2})$ update time and $\tilde{O}(n^{2/3}\varepsilon^{-2})$ query time. We also extend this algorithm to work for minor-free graphs with similar approximation and running time guarantees. Furthermore, we illustrate our framework on the all-pairs max flow and shortest path problems by giving corresponding dynamic algorithms in minor-free graphs with both sublinear update and query times. To the best of our knowledge, our results are the first to systematically establish such a connection between dynamic graph algorithms and vertex sparsification. We also present both upper bound and lower bound for maintaining the energy of electrical flows in the incremental subgraph model, where updates consist of only vertex activations, which might be of independent interest.
On the Relationship Between the OpenAI Evolution Strategy and Stochastic Gradient Descent
Venue: arXiv cs.NE 2017
Year: 2017

Because stochastic gradient descent (SGD) has shown promise optimizing neural networks with millions of parameters and few if any alternatives are known to exist, it has moved to the heart of leading approaches to reinforcement learning (RL). For that reason, the recent result from OpenAI showing that a particular kind of evolution strategy (ES) can rival the performance of SGD-based deep RL methods with large neural networks provoked surprise. This result is difficult to interpret in part because of the lingering ambiguity on how ES actually relates to SGD. The aim of this paper is to significantly reduce this ambiguity through a series of MNIST-based experiments designed to uncover their relationship. As a simple supervised problem without domain noise (unlike in most RL), MNIST makes it possible (1) to measure the correlation between gradients computed by ES and SGD and (2) then to develop an SGD-based proxy that accurately predicts the performance of different ES population sizes. These innovations give a new level of insight into the real capabilities of ES, and lead also to some unconventional means for applying ES to supervised problems that shed further light on its differences from SGD. Incorporating these lessons, the paper concludes by demonstrating that ES can achieve 99% accuracy on MNIST, a number higher than any previously published result for any evolutionary method. While not by any means suggesting that ES should substitute for SGD in supervised learning, the suite of experiments herein enables more informed decisions on the application of ES within RL and other paradigms.
Solving satisfiability using inclusion-exclusion
Venue: arXiv cs.DS 2017
Year: 2017

Using Maple, we implement a SAT solver based on the principle of inclusion-exclusion and the Bonferroni inequalities. Using randomly generated input, we investigate the performance of our solver as a function of the number of variables and number of clauses. We also test it against Maple's built-in tautology procedure. Finally, we implement the Lovász local lemma with Maple and discuss its applicability to SAT.
Fast Algorithms for Delta-Separated Sparsity Projection
Venue: arXiv cs.DS 2017
Year: 2017

We describe a fast approximation algorithm for the $Δ$-separated sparsity projection problem. The $Δ$-separated sparsity model was introduced by Hegde, Duarte and Cevher (2009) to capture the firing process of a single Poisson neuron with absolute refractoriness. The running time of our projection algorithm is linear for an arbitrary (but fixed) precision and it is both a head and a tail approximation. This solves a problem of Hegde, Indyk and Schmidt (2015). We also describe how our algorithm fits into the approximate model iterative hard tresholding framework of Hegde, Indyk and Schmidt (2014) that allows to recover $Δ$-separated sparse signals from noisy random linear measurements. The resulting recovery algorithm is substantially faster than the existing one, at least for large data sets.
Approximate Correlation Clustering Using Same-Cluster Queries
Venue: arXiv cs.DS 2017
Year: 2017

Ashtiani et al. (NIPS 2016) introduced a semi-supervised framework for clustering (SSAC) where a learner is allowed to make same-cluster queries. More specifically, in their model, there is a query oracle that answers queries of the form given any two vertices, do they belong to the same optimal cluster?. Ashtiani et al. showed the usefulness of such a query framework by giving a polynomial time algorithm for the k-means clustering problem where the input dataset satisfies some separation condition. Ailon et al. extended the above work to the approximation setting by giving an efficient (1+\eps)-approximation algorithm for k-means for any small \eps > 0 and any dataset within the SSAC framework. In this work, we extend this line of study to the correlation clustering problem. Correlation clustering is a graph clustering problem where pairwise similarity (or dissimilarity) information is given for every pair of vertices and the objective is to partition the vertices into clusters that minimise the disagreement (or maximises agreement) with the pairwise information given as input. These problems are popularly known as MinDisAgree and MaxAgree problems, and MinDisAgree[k] and MaxAgree[k] are versions of these problems where the number of optimal clusters is at most k. There exist Polynomial Time Approximation Schemes (PTAS) for MinDisAgree[k] and MaxAgree[k] where the approximation guarantee is (1+\eps) for any small \eps and the running time is polynomial in the input parameters but exponential in k and 1/\eps. We obtain an (1+\eps)-approximation algorithm for any small \eps with running time that is polynomial in the input parameters and also in k and 1/\eps. We also give non-trivial upper and lower bounds on the number of same-cluster queries, the lower bound being based on the Exponential Time Hypothesis (ETH).
Effects of update rules on networked N-player trust game dynamics
Venue: arXiv cs.GT 2017
Year: 2017

We investigate the effects of update rules on the dynamics of an evolutionary game-theoretic model - the N-player evolutionary trust game - consisting of three types of players: investors, trustworthy trustees, and untrustworthy trustees. Interactions between players are limited to local neighborhoods determined by predefined spatial or social network topologies. We compare evolutionary update rules based on the payoffs obtained by their neighbors. Specifically, we investigate the dynamics generated when players use a deterministic strategic rule (i.e., unconditional imitation with and without using a noise process induced by a voter model), a stochastic pairwise payoff-based strategy (i.e., proportional imitation), and stochastic local Moran processes. We explore the system dynamics under these update rules based on different social networks and different levels of game difficulty. We observe that there are significant differences on the promoted trust and global net wealth depending on the update rule. If the game is harder, rules based on unconditional imitation achieve the highest global net wealth in the population. Besides a global perspective, we also study the spatial and temporal dynamics induced by the rules and we find important spatio-temporal correlations in the system for all rules. Indeed, the update rules lead to the formation of fractal structures on a lattice and, when the rules are stochastic, also the emergence of low frequencies in the output signal of the system (i.e., long-term memory).
Analogy Mining for Specific Design Needs
Venue: arXiv cs.CL 2017
Year: 2017

Finding analogical inspirations in distant domains is a powerful way of solving problems. However, as the number of inspirations that could be matched and the dimensions on which that matching could occur grow, it becomes challenging for designers to find inspirations relevant to their needs. Furthermore, designers are often interested in exploring specific aspects of a product-- for example, one designer might be interested in improving the brewing capability of an outdoor coffee maker, while another might wish to optimize for portability. In this paper we introduce a novel system for targeting analogical search for specific needs. Specifically, we contribute a novel analogical search engine for expressing and abstracting specific design needs that returns more distant yet relevant inspirations than alternate approaches.
Learning Fixation Point Strategy for Object Detection and Classification
Venue: arXiv cs.CV 2017
Year: 2017

We propose a novel recurrent attentional structure to localize and recognize objects jointly. The network can learn to extract a sequence of local observations with detailed appearance and rough context, instead of sliding windows or convolutions on the entire image. Meanwhile, those observations are fused to complete detection and classification tasks. On training, we present a hybrid loss function to learn the parameters of the multi-task network end-to-end. Particularly, the combination of stochastic and object-awareness strategy, named SA, can select more abundant context and ensure the last fixation close to the object. In addition, we build a real-world dataset to verify the capacity of our method in detecting the object of interest including those small ones. Our method can predict a precise bounding box on an image, and achieve high speed on large images without pooling operations. Experimental results indicate that the proposed method can mine effective context by several local observations. Moreover, the precision and speed are easily improved by changing the number of recurrent steps. Finally, we will open the source code of our proposed approach.
Accelerating the computation of FLAPW methods on heterogeneous architectures
Venue: arXiv cs.DC 2017
Year: 2017

Legacy codes in computational science and engineering have been very successful in providing essential functionality to researchers. However, they are not capable of exploiting the massive parallelism provided by emerging heterogeneous architectures. The lack of portable performance and scalability puts them at high risk: either they evolve or they are doomed to disappear. One example of legacy code which would heavily benefit from a modern design is FLEUR, a software for electronic structure calculations. In previous work, the computational bottleneck of FLEUR was partially re-engineered to have a modular design that relies on standard building blocks, namely BLAS and LAPACK. In this paper, we demonstrate how the initial redesign enables the portability to heterogeneous architectures. More specifically, we study different approaches to port the code to architectures consisting of multi-core CPUs equipped with one or more coprocessors such as Nvidia GPUs and Intel Xeon Phis. Our final code attains over 70\% of the architectures' peak performance, and outperforms Nvidia's and Intel's libraries. Finally, on JURECA, the supercomputer where FLEUR is often executed, the code takes advantage of the full power of the computing nodes, attaining $5\times$ speedup over the sole use of the CPUs.
Fast Quantum Algorithm for Solving Multivariate Quadratic Equations
Venue: arXiv cs.CR 2017
Year: 2017

In August 2015 the cryptographic world was shaken by a sudden and surprising announcement by the US National Security Agency NSA concerning plans to transition to post-quantum algorithms. Since this announcement post-quantum cryptography has become a topic of primary interest for several standardization bodies. The transition from the currently deployed public-key algorithms to post-quantum algorithms has been found to be challenging in many aspects. In particular the problem of evaluating the quantum-bit security of such post-quantum cryptosystems remains vastly open. Of course this question is of primarily concern in the process of standardizing the post-quantum cryptosystems. In this paper we consider the quantum security of the problem of solving a system of {\it $m$ Boolean multivariate quadratic equations in $n$ variables} (\MQb); a central problem in post-quantum cryptography. When $n=m$, under a natural algebraic assumption, we present a Las-Vegas quantum algorithm solving \MQb{} that requires the evaluation of, on average, $O(2^{0.462n})$ quantum gates. To our knowledge this is the fastest algorithm for solving \MQb{}.
Revisiting the Master-Slave Architecture in Multi-Agent Deep Reinforcement Learning
Venue: arXiv cs.AI 2017
Year: 2017

Many tasks in artificial intelligence require the collaboration of multiple agents. We exam deep reinforcement learning for multi-agent domains. Recent research efforts often take the form of two seemingly conflicting perspectives, the decentralized perspective, where each agent is supposed to have its own controller; and the centralized perspective, where one assumes there is a larger model controlling all agents. In this regard, we revisit the idea of the master-slave architecture by incorporating both perspectives within one framework. Such a hierarchical structure naturally leverages advantages from one another. The idea of combining both perspectives is intuitive and can be well motivated from many real world systems, however, out of a variety of possible realizations, we highlights three key ingredients, i.e. composed action representation, learnable communication and independent reasoning. With network designs to facilitate these explicitly, our proposal consistently outperforms latest competing methods both in synthetic experiments and when applied to challenging StarCraft micromanagement tasks.