OpenRaiser/Intern-Atlas huggingface dataset:
Approximate Privacy-Preserving Neighbourhood Estimations
Venue: arXiv cs.DS 2021
Year: 2021

Anonymous social networks present a number of new and challenging problems for existing Social Network Analysis techniques. Traditionally, existing methods for analysing graph structure, such as community detection, required global knowledge of the graph structure. That implies that a centralised entity must be given access to the edge list of each node in the graph. This is impossible for anonymous social networks and other settings where privacy is valued by its participants. In addition, using their graph structure inputs for learning tasks defeats the purpose of anonymity. In this work, we hypothesise that one can re-purpose the use of the HyperANF a.k.a HyperBall algorithm -- intended for approximate diameter estimation -- to the task of privacy-preserving community detection for friend recommending systems that learn from an anonymous representation of the social network graph structure with limited privacy impact. This is possible because the core data structure maintained by HyperBall is a HyperLogLog with a counter of the number of reachable neighbours from a given node. Exchanging this data structure in future decentralised learning deployments gives away no information about the neighbours of the node and therefore does preserve the privacy of the graph structure.
Modular Object-Oriented Games: A Task Framework for Reinforcement Learning, Psychology, and Neuroscience
Venue: arXiv cs.AI 2021
Year: 2021

In recent years, trends towards studying simulated games have gained momentum in the fields of artificial intelligence, cognitive science, psychology, and neuroscience. The intersections of these fields have also grown recently, as researchers increasing study such games using both artificial agents and human or animal subjects. However, implementing games can be a time-consuming endeavor and may require a researcher to grapple with complex codebases that are not easily customized. Furthermore, interdisciplinary researchers studying some combination of artificial intelligence, human psychology, and animal neurophysiology face additional challenges, because existing platforms are designed for only one of these domains. Here we introduce Modular Object-Oriented Games, a Python task framework that is lightweight, flexible, customizable, and designed for use by machine learning, psychology, and neurophysiology researchers.
Protograph-Based Design for QC Polar Codes
Venue: arXiv cs.IT 2021
Year: 2021

We propose a new family of polar coding which realizes high coding gain, low complexity, and high throughput by introducing a protograph-based design. The proposed technique called as quasi-cyclic (QC) polar codes can be highly parallelized without sacrificing decoding complexity. We analyze short cycles in the protograph polar codes and develop a design method to increase the girth. Our approach can resolve the long-standing unsolved problem that belief propagation (BP) decoding does not work well for polar codes due to the inherently short cycles. We demonstrate that a high lifting factor of QC polar codes can improve the performance and that QC polar codes with BP decoding can outperform conventional polar codes with state-of-the-art list decoding. Moreover, we show that a greedy pruning method can improve the performance-complexity trade-off.
Theory and Analysis of Optimal Planning over Long and Infinite Horizons for Achieving Independent Partially-Observable Tasks that Evolve over Time
Venue: arXiv cs.RO 2021
Year: 2021

We present the theoretical analysis and proofs of a recently developed algorithm that allows for optimal planning over long and infinite horizons for achieving multiple independent tasks that are partially observable and evolve over time.
Automatic Story Generation: Challenges and Attempts
Venue: arXiv cs.CL 2021
Year: 2021

The scope of this survey paper is to explore the challenges in automatic story generation. We hope to contribute in the following ways: 1. Explore how previous research in story generation addressed those challenges. 2. Discuss future research directions and new technologies that may aid more advancements. 3. Shed light on emerging and often overlooked challenges such as creativity and discourse.
Spanning Tree Constrained Determinantal Point Processes are Hard to (Approximately) Evaluate
Venue: arXiv cs.LG 2021
Year: 2021

We consider determinantal point processes (DPPs) constrained by spanning trees. Given a graph $G=(V,E)$ and a positive semi-definite matrix $\mathbf{A}$ indexed by $E$, a spanning-tree DPP defines a distribution such that we draw $S\subseteq E$ with probability proportional to $\det(\mathbf{A}_S)$ only if $S$ induces a spanning tree. We prove $\sharp\textsf{P}$-hardness of computing the normalizing constant for spanning-tree DPPs and provide an approximation-preserving reduction from the mixed discriminant, for which FPRAS is not known. We show similar results for DPPs constrained by forests.
Deep Stochastic Volatility Model
Venue: arXiv cs.LG 2021
Year: 2021

Volatility for financial assets returns can be used to gauge the risk for financial market. We propose a deep stochastic volatility model (DSVM) based on the framework of deep latent variable models. It uses flexible deep learning models to automatically detect the dependence of the future volatility on past returns, past volatilities and the stochastic noise, and thus provides a flexible volatility model without the need to manually select features. We develop a scalable inference and learning algorithm based on variational inference. In real data analysis, the DSVM outperforms several popular alternative volatility models. In addition, the predicted volatility of the DSVM provides a more reliable risk measure that can better reflex the risk in the financial market, reaching more quickly to a higher level when the market becomes more risky and to a lower level when the market is more stable, compared with the commonly used GARCH type model with a huge data set on the U.S. stock market.
Learning Inverse Kinodynamics for Accurate High-Speed Off-Road Navigation on Unstructured Terrain
Venue: arXiv cs.RO 2021
Year: 2021

This paper presents a learning-based approach to consider the effect of unobservable world states in kinodynamic motion planning in order to enable accurate high-speed off-road navigation on unstructured terrain. Existing kinodynamic motion planners either operate in structured and homogeneous environments and thus do not need to explicitly account for terrain-vehicle interaction, or assume a set of discrete terrain classes. However, when operating on unstructured terrain, especially at high speeds, even small variations in the environment will be magnified and cause inaccurate plan execution. In this paper, to capture the complex kinodynamic model and mathematically unknown world state, we learn a kinodynamic planner in a data-driven manner with onboard inertial observations. Our approach is tested on a physical robot in different indoor and outdoor environments, enables fast and accurate off-road navigation, and outperforms environment-independent alternatives, demonstrating 52.4% to 86.9% improvement in terms of plan execution success rate while traveling at high speeds.
Sentiment Analysis of Persian-English Code-mixed Texts
Venue: arXiv cs.CL 2021
Year: 2021

The rapid production of data on the internet and the need to understand how users are feeling from a business and research perspective has prompted the creation of numerous automatic monolingual sentiment detection systems. More recently however, due to the unstructured nature of data on social media, we are observing more instances of multilingual and code-mixed texts. This development in content type has created a new demand for code-mixed sentiment analysis systems. In this study we collect, label and thus create a dataset of Persian-English code-mixed tweets. We then proceed to introduce a model which uses BERT pretrained embeddings as well as translation models to automatically learn the polarity scores of these Tweets. Our model outperforms the baseline models that use Naïve Bayes and Random Forest methods.
What's in a GitHub Repository? -- A Software Documentation Perspective
Venue: arXiv cs.SE 2021
Year: 2021

Developers use and contribute to repositories on GitHub. Documentation present in the repositories serves as an important source by helping developers to understand, maintain and contribute to the project. Currently, documentation in a repository is diversified, among various files, with most of it present in ReadMe files. However, other software artifacts in the repository, such as issue reports and pull requests could also contribute to documentation, without documentation being explicitly specified. Hence, in this paper, we propose a taxonomy of documentation sources by analyzing different software artifacts, developer interviews and card-sorting approach. We inspected multiple artifacts of 950 public GitHub repositories, written in four different programming languages, C++, C#, Python and Java, and analyzed the type and amount of documentation that could be extracted from these artifacts. To this end, we observe that, about 25.93% of information extracted from all sources proposed in the taxonomy contains error-related documentation, and that pull requests contribute to around 18.21% of extracted information.
Scene Retrieval for Contextual Visual Mapping
Venue: arXiv cs.CV 2021
Year: 2021

Visual navigation localizes a query place image against a reference database of place images, also known as a `visual map'. Localization accuracy requirements for specific areas of the visual map, `scene classes', vary according to the context of the environment and task. State-of-the-art visual mapping is unable to reflect these requirements by explicitly targetting scene classes for inclusion in the map. Four different scene classes, including pedestrian crossings and stations, are identified in each of the Nordland and St. Lucia datasets. Instead of re-training separate scene classifiers which struggle with these overlapping scene classes we make our first contribution: defining the problem of `scene retrieval'. Scene retrieval extends image retrieval to classification of scenes defined at test time by associating a single query image to reference images of scene classes. Our second contribution is a triplet-trained convolutional neural network (CNN) to address this problem which increases scene classification accuracy by up to 7% against state-of-the-art networks pre-trained for scene recognition. The second contribution is an algorithm `DMC' that combines our scene classification with distance and memorability for visual mapping. Our analysis shows that DMC includes 64% more images of our chosen scene classes in a visual map than just using distance interval mapping. State-of-the-art visual place descriptors AMOS-Net, Hybrid-Net and NetVLAD are finally used to show that DMC improves scene class localization accuracy by a mean of 3% and localization accuracy of the remaining map images by a mean of 10% across both datasets.
Blockchained Federated Learning for Threat Defense
Venue: arXiv cs.CR 2021
Year: 2021

Given the increasing complexity of threats in smart cities, the changing environment, and the weakness of traditional security systems, which in most cases fail to detect serious threats such as zero-day attacks, the need for alternative more active and more effective security methods keeps increasing. Such approaches are the adoption of intelligent solutions to prevent, detect and deal with threats or anomalies under the conditions and the operating parameters of the infrastructure in question. This research paper introduces the development of an intelligent Threat Defense system, employing Blockchain Federated Learning, which seeks to fully upgrade the way passive intelligent systems operate, aiming at implementing an Advanced Adaptive Cooperative Learning (AACL) mechanism for smart cities networks. The AACL is based on the most advanced methods of computational intelligence while ensuring privacy and anonymity for participants and stakeholders. The proposed framework combines Federated Learning for the distributed and continuously validated learning of the tracing algorithms. Learning is achieved through encrypted smart contracts within the blockchain technology, for unambiguous validation and control of the process. The aim of the proposed Framework is to intelligently classify smart cities networks traffic derived from Industrial IoT (IIoT) by Deep Content Inspection (DCI) methods, in order to identify anomalies that are usually due to Advanced Persistent Threat (APT) attacks.
ZJUKLAB at SemEval-2021 Task 4: Negative Augmentation with Language Model for Reading Comprehension of Abstract Meaning
Venue: arXiv cs.CL 2021
Year: 2021

This paper presents our systems for the three Subtasks of SemEval Task4: Reading Comprehension of Abstract Meaning (ReCAM). We explain the algorithms used to learn our models and the process of tuning the algorithms and selecting the best model. Inspired by the similarity of the ReCAM task and the language pre-training, we propose a simple yet effective technology, namely, negative augmentation with language model. Evaluation results demonstrate the effectiveness of our proposed approach. Our models achieve the 4th rank on both official test sets of Subtask 1 and Subtask 2 with an accuracy of 87.9% and an accuracy of 92.8%, respectively. We further conduct comprehensive model analysis and observe interesting error cases, which may promote future researches.
Are Anti-Feminist Communities Gateways to the Far Right? Evidence from Reddit and YouTube
Venue: arXiv cs.CY 2021
Year: 2021

Researchers have suggested that "the Manosphere," a conglomerate of men-centered online communities, may serve as a gateway to far right movements. In that context, this paper quantitatively studies the migratory patterns between a variety of groups within the Manosphere and the Alt-right, a loosely connected far right movement that has been particularly active in mainstream social networks. Our analysis leverages over 300 million comments spread through Reddit (in 115 subreddits) and YouTube (in 526 channels) to investigate whether the audiences of channels and subreddits associated with these communities have converged between 2006 and 2018. In addition to subreddits related to the communities of interest, we also collect data on counterparts: other groups of users which we use for comparison (e.g., for YouTube we use a set of media channels). Besides measuring the similarity in the commenting user bases of these communities, we perform a migration study, calculating to which extent users in the Manosphere gradually engage with Alt-right content. Our results suggest that there is a large overlap between the user bases of the Alt-right and of the Manosphere and that members of the Manosphere have a bigger chance to engage with far right content than carefully chosen counterparts. However, our analysis also shows that migration and user base overlap varies substantially across different platforms and within the Manosphere. Members of some communities (e.g., Men's Rights Activists) gradually engage with the Alt-right significantly more than counterparts on both Reddit and YouTube, whereas for other communities, this engagement happens mostly on Reddit (e.g., Pick Up Artists). Overall, our work paints a nuanced picture of the pipeline between the Manosphere and the Alt-right, which may inform platforms' policies and moderation decisions regarding these communities.
Generalized Adversarial Distances to Efficiently Discover Classifier Errors
Venue: arXiv cs.LG 2021
Year: 2021

Given a black-box classification model and an unlabeled evaluation dataset from some application domain, efficient strategies need to be developed to evaluate the model. Random sampling allows a user to estimate metrics like accuracy, precision, and recall, but may not provide insight to high-confidence errors. High-confidence errors are rare events for which the model is highly confident in its prediction, but is wrong. Such errors can represent costly mistakes and should be explicitly searched for. In this paper we propose a generalization to the Adversarial Distance search that leverages concepts from adversarial machine learning to identify predictions for which a classifier may be overly confident. These predictions are useful instances to sample when looking for high-confidence errors because they are prone to a higher rate of error than expected. Our generalization allows Adversarial Distance to be applied to any classifier or data domain. Experimental results show that the generalized method finds errors at rates greater than expected given the confidence of the sampled predictions, and outperforms competing methods.
Understanding Worldwide Private Information Collection on Android
Venue: arXiv cs.CR 2021
Year: 2021

Mobile phones enable the collection of a wealth of private information, from unique identifiers (e.g., email addresses), to a user's location, to their text messages. This information can be harvested by apps and sent to third parties, which can use it for a variety of purposes. In this paper we perform the largest study of private information collection (PIC) on Android to date. Leveraging an anonymized dataset collected from the customers of a popular mobile security product, we analyze the flows of sensitive information generated by 2.1M unique apps installed by 17.3M users over a period of 21 months between 2018 and 2019. We find that 87.2% of all devices send private information to at least five different domains, and that actors active in different regions (e.g., Asia compared to Europe) are interested in collecting different types of information. The United States (62% of the total) and China (7% of total flows) are the countries that collect most private information. Our findings raise issues regarding data regulation, and would encourage policymakers to further regulate how private information is used by and shared among the companies and how accountability can be truly guaranteed.
A Refined Analysis of Submodular Greedy
Venue: arXiv cs.DS 2021
Year: 2021

Many algorithms for maximizing a monotone submodular function subject to a knapsack constraint rely on the natural greedy heuristic. We present a novel refined analysis of this greedy heuristic which enables us to: $(1)$ reduce the enumeration in the tight $(1-e^{-1})$-approximation of [Sviridenko 04] from subsets of size three to two; $(2)$ present an improved upper bound of $0.42945$ for the classic algorithm which returns the better between a single element and the output of the greedy heuristic.
Predicting times of waiting on red signals using BERT
Venue: arXiv cs.LG 2021
Year: 2021

We present a method for approximating outcomes of road traffic simulations using BERT-based models, which may find applications in, e.g., optimizing traffic signal settings, especially with the presence of autonomous and connected vehicles. The experiments were conducted on a dataset generated using the Traffic Simulation Framework software runs on a realistic road network. The BERT-based models were compared with 4 other types of machine learning models (LightGBM, fully connected neural networks and 2 types of graph neural networks) and gave the best results in terms of all the considered metrics.
Fresh, Fair and Energy-Efficient Content Provision in a Private and Cache-Enabled UAV Network
Venue: arXiv cs.NI 2021
Year: 2021

In this paper, we investigate a private and cache-enabled unmanned aerial vehicle (UAV) network for content provision. Aiming at delivering fresh, fair, and energy-efficient content files to terrestrial users, we formulate a joint UAV caching, UAV trajectory, and UAV transmit power optimization problem. This problem is confirmed to be a sequential decision problem with mixed-integer non-convex constraints, which is intractable directly. To this end, we propose a novel algorithm based on the techniques of subproblem decomposition and convex approximation. Particularly, we first propose to decompose the sequential decision problem into multiple repeated optimization subproblems via a Lyapunov technique. Next, an iterative optimization scheme incorporating a successive convex approximation (SCA) technique is explored to tackle the challenging mixed-integer non-convex subproblems. Besides, we analyze the convergence and computational complexity of the proposed algorithm and derive the theoretical value of the expected peak age of information (PAoI) to estimate the content freshness. Simulation results demonstrate that the proposed algorithm can achieve the expected PAoI close to the theoretical value and is more 22.11% and 70.51% energy-efficient and fairer than benchmark algorithms.
Visualizing MuZero Models
Venue: arXiv cs.LG 2021
Year: 2021

MuZero, a model-based reinforcement learning algorithm that uses a value equivalent dynamics model, achieved state-of-the-art performance in Chess, Shogi and the game of Go. In contrast to standard forward dynamics models that predict a full next state, value equivalent models are trained to predict a future value, thereby emphasizing value relevant information in the representations. While value equivalent models have shown strong empirical success, there is no research yet that visualizes and investigates what types of representations these models actually learn. Therefore, in this paper we visualize the latent representation of MuZero agents. We find that action trajectories may diverge between observation embeddings and internal state transition dynamics, which could lead to instability during planning. Based on this insight, we propose two regularization techniques to stabilize MuZero's performance. Additionally, we provide an open-source implementation of MuZero along with an interactive visualizer of learned representations, which may aid further investigation of value equivalent algorithms.
Graph Exploration by Energy-Sharing Mobile Agents
Venue: arXiv cs.DM 2021
Year: 2021

We consider the problem of collective exploration of a known $n$-node edge-weighted graph by $k$ mobile agents that have limited energy but are capable of energy transfers. The agents are initially placed at an arbitrary subset of nodes in the graph, and each agent has an initial, possibly different, amount of energy. The goal of the exploration problem is for every edge in the graph to be traversed by at least one agent. The amount of energy used by an agent to travel distance $x$ is proportional to $x$. In our model, the agents can {\em share} energy when co-located: when two agents meet, one can transfer part of its energy to the other. For an $n$-node path, we give an $O(n+k)$ time algorithm that either finds an exploration strategy, or reports that one does not exist. For an $n$-node tree with $\ell $ leaves, we give an $O(n+ \ell k^2)$ algorithm that finds an exploration strategy if one exists. Finally, for the general graph case, we show that the problem of deciding if exploration is possible by energy-sharing agents is NP-hard, even for 3-regular graphs. In addition, we show that it is always possible to find an exploration strategy if the total energy of the agents is at least twice the total weight of the edges; moreover, this is asymptotically optimal.