OpenRaiser/Intern-Atlas huggingface dataset:
Session Types with Arithmetic Refinements and Their Application to Work Analysis
Venue: arXiv cs.PL 2020
Year: 2020

Session types statically prescribe bidirectional communication protocols for message-passing processes and are in a Curry-Howard correspondence with linear logic propositions. However, simple session types cannot specify properties beyond the type of exchanged messages. In this paper we extend the type system by using index refinements from linear arithmetic capturing intrinsic attributes of data structures and algorithms so that we can express and verify amortized cost of programs using ergometric types. We show that, despite the decidability of Presburger arithmetic, type equality and therefore also type checking are now undecidable, which stands in contrast to analogous dependent refinement type systems from functional languages. We also present a practical incomplete algorithm for type equality and an algorithm for type checking which is complete relative to an oracle for type equality. Process expressions in this explicit language are rather verbose, so we also introduce an implicit form and a sound and complete algorithm for reconstructing explicit programs, borrowing ideas from the proof-theoretic technique of focusing. We conclude by illustrating our systems and algorithms with a variety of examples that have been verified in our implementation.
Donald Duck Holiday Game: A numerical analysis of a Game of the Goose role-playing variant
Venue: arXiv cs.CY 2020
Year: 2020

The 1996 Donald Duck Holiday Game is a role-playing variant of the historical Game of the Goose, involving characters with unique attributes, event squares, and random event cards. The objective of the game is to reach the camping before any other player does. We develop a Monte Carlo simulation model that automatically plays the game and enables analyzing its key characteristics. We assess the game on various metrics relevant to each playability. Numerical analysis shows that, on average, the game takes between 69 and 123 rounds to complete, depending on the number of players. However, durations over one hour (translated to human play time) occur over 25% of the games, which might reduce the quality of the gaming experience. Furthermore, we show that two characters are about 30% likely to win than the other three, primarily due to being exposed to fewer random events. We argue that the richer narrative of role-playing games may extend the duration for which the game remains enjoyable, such that the metrics cannot directly be compared to those of the traditional Game-of-the-Goose. Based on our analysis, we provide several suggestions to improve the game balance with only slight modifications. In a broader sense, we demonstrate that a basic Monte Carlo simulation suffices to analyze Game-of-the-Goose role-playing variants, verify how they score on criteria that contribute to an enjoyable game, and detect possible anomalies.
Learning Transformation-Aware Embeddings for Image Forensics
Venue: arXiv cs.CV 2020
Year: 2020

A dramatic rise in the flow of manipulated image content on the Internet has led to an aggressive response from the media forensics research community. New efforts have incorporated increased usage of techniques from computer vision and machine learning to detect and profile the space of image manipulations. This paper addresses Image Provenance Analysis, which aims at discovering relationships among different manipulated image versions that share content. One of the main sub-problems for provenance analysis that has not yet been addressed directly is the edit ordering of images that share full content or are near-duplicates. The existing large networks that generate image descriptors for tasks such as object recognition may not encode the subtle differences between these image covariates. This paper introduces a novel deep learning-based approach to provide a plausible ordering to images that have been generated from a single image through transformations. Our approach learns transformation-aware descriptors using weak supervision via composited transformations and a rank-based quadruplet loss. To establish the efficacy of the proposed approach, comparisons with state-of-the-art handcrafted and deep learning-based descriptors, and image matching approaches are made. Further experimentation validates the proposed approach in the context of image provenance analysis.
A survey on Machine Learning-based Performance Improvement of Wireless Networks: PHY, MAC and Network layer
Venue: arXiv cs.LG 2020
Year: 2020

This paper provides a systematic and comprehensive survey that reviews the latest research efforts focused on machine learning (ML) based performance improvement of wireless networks, while considering all layers of the protocol stack (PHY, MAC and network). First, the related work and paper contributions are discussed, followed by providing the necessary background on data-driven approaches and machine learning for non-machine learning experts to understand all discussed techniques. Then, a comprehensive review is presented on works employing ML-based approaches to optimize the wireless communication parameters settings to achieve improved network quality-of-service (QoS) and quality-of-experience (QoE). We first categorize these works into: radio analysis, MAC analysis and network prediction approaches, followed by subcategories within each. Finally, open challenges and broader perspectives are discussed.
Monte Carlo Anti-Differentiation for Approximate Weighted Model Integration
Venue: arXiv cs.AI 2020
Year: 2020

Probabilistic inference in the hybrid domain, i.e. inference over discrete-continuous domains, requires tackling two well known #P-hard problems 1)~weighted model counting (WMC) over discrete variables and 2)~integration over continuous variables. For both of these problems inference techniques have been developed separately in order to manage their #P-hardness, such as knowledge compilation for WMC and Monte Carlo (MC) methods for (approximate) integration in the continuous domain. Weighted model integration (WMI), the extension of WMC to the hybrid domain, has been proposed as a formalism to study probabilistic inference over discrete and continuous variables alike. Recently developed WMI solvers have focused on exploiting structure in WMI problems, for which they rely on symbolic integration to find the primitive of an integrand, i.e. to perform anti-differentiation. To combine these advances with state-of-the-art Monte Carlo integration techniques, we introduce \textit{Monte Carlo anti-differentiation} (MCAD), which computes MC approximations of anti-derivatives. In our empirical evaluation we substitute the exact symbolic integration backend in an existing WMI solver with an MCAD backend. Our experiments show that that equipping existing WMI solvers with MCAD yields a fast yet reliable approximate inference scheme.
Preliminary Study of a Google Home Mini
Venue: arXiv cs.CY 2020
Year: 2020

Many artificial intelligence (AI) speakers have recently come to market. Beginning with Amazon Echo, many companies producing their own speaker technologies. Due to the limitations of technology, most speakers have similar functions, but the way of handling the data of each speaker is different. In the case of Amazon echo, the API of the cloud is open for any developers to develop their API. The Amazon Echo has been around for a while, and much research has been done on it. However, not much research has been done on Google Home Mini analysis for digital investigations. In this paper, we will conduct some initial research on the data storing and security methods of Google Home Mini.
Asymmetric Correlation Quantization Hashing for Cross-modal Retrieval
Venue: arXiv cs.IR 2020
Year: 2020

Due to the superiority in similarity computation and database storage for large-scale multiple modalities data, cross-modal hashing methods have attracted extensive attention in similarity retrieval across the heterogeneous modalities. However, there are still some limitations to be further taken into account: (1) most current CMH methods transform real-valued data points into discrete compact binary codes under the binary constraints, limiting the capability of representation for original data on account of abundant loss of information and producing suboptimal hash codes; (2) the discrete binary constraint learning model is hard to solve, where the retrieval performance may greatly reduce by relaxing the binary constraints for large quantization error; (3) handling the learning problem of CMH in a symmetric framework, leading to difficult and complex optimization objective. To address above challenges, in this paper, a novel Asymmetric Correlation Quantization Hashing (ACQH) method is proposed. Specifically, ACQH learns the projection matrixs of heterogeneous modalities data points for transforming query into a low-dimensional real-valued vector in latent semantic space and constructs the stacked compositional quantization embedding in a coarse-to-fine manner for indicating database points by a series of learnt real-valued codeword in the codebook with the help of pointwise label information regression simultaneously. Besides, the unified hash codes across modalities can be directly obtained by the discrete iterative optimization framework devised in the paper. Comprehensive experiments on diverse three benchmark datasets have shown the effectiveness and rationality of ACQH.
A Network Formation Game for the Emergence of Hierarchies
Venue: arXiv cs.GT 2020
Year: 2020

We propose a novel network formation game that explains the emergence of various hierarchical structures in groups where self-interested or utility-maximizing individuals decide to establish or severe relationships of authority or collaboration among themselves. We consider two settings: we first consider individuals who do not seek the other party's consent when establishing a relationship and then individuals who do. For both settings, we formally relate the emerged hierarchical structures with the novel inclusion of well-motivated hierarchy promoting terms in the individuals' utility functions. We first analyze the game via a static analysis and characterize all the hierarchical structures that can be formed as its solutions. We then consider the game played dynamically under stochastic interactions among individuals implementing better-response dynamics and analyze the nature of the converged networks.
Balancing the composition of word embeddings across heterogenous data sets
Venue: arXiv cs.CL 2020
Year: 2020

Word embeddings capture semantic relationships based on contextual information and are the basis for a wide variety of natural language processing applications. Notably these relationships are solely learned from the data and subsequently the data composition impacts the semantic of embeddings which arguably can lead to biased word vectors. Given qualitatively different data subsets, we aim to align the influence of single subsets on the resulting word vectors, while retaining their quality. In this regard we propose a criteria to measure the shift towards a single data subset and develop approaches to meet both objectives. We find that a weighted average of the two subset embeddings balances the influence of those subsets while word similarity performance decreases. We further propose a promising optimization approach to balance influences and quality of word embeddings.
Online Scheduling with Makespan Minimization: State of the Art Results, Research Challenges and Open Problems
Venue: arXiv cs.OS 2020
Year: 2020

Online scheduling has been a well studied and challenging research problem over the last five decades since the pioneering work of Graham with immense practical significance in various applications such as interactive parallel processing, routing in communication networks, distributed data management, client-server communications, traffic management in transportation, industrial manufacturing and production. In this problem, a sequence of jobs is received one by one in order by the scheduler for scheduling over a number of machines. On arrival of a job, the scheduler assigns the job irrevocably to a machine before the availability of the next job with an objective to minimize the completion time of the scheduled jobs. This paper highlights the state of the art contributions for online scheduling of a sequence of independent jobs on identical and uniform related machines with a special focus on preemptive and non-preemptive processing formats by considering makespan minimization as the optimality criterion. We present the fundamental aspects of online scheduling from a beginner's perspective along with a background of general scheduling framework. Important competitive analysis results obtained by well-known deterministic and randomized online scheduling algorithms in the literature are presented along with research challenges and open problems. Two of the emerging recent trends such as resource augmentation and semi-online scheduling are discussed as a motivation for future research work.
Change Detection in Dynamic Attributed Networks
Venue: arXiv cs.SI 2020
Year: 2020

A network provides powerful means of representing complex relationships between entities by abstracting entities as vertices, and relationships as edges connecting vertices in a graph. Beyond the presence or absence of relationships, a network may contain additional information that can be attributed to the entities and their relationships. Attaching these additional attribute data to the corresponding vertices and edges yields an attributed graph. Moreover, in the majority of real-world applications, such as online social networks, financial networks and transactional networks, relationships between entities evolve over time. Change detection in dynamic attributed networks is an important problem in many areas, such as fraud detection, cyber intrusion detection and health care monitoring. It is a challenging problem because it involves a time sequence of attributed graphs, each of which is usually very large and can contain many attributes attached to the vertices and edges, resulting in a complex, high dimensional mathematical object. In this survey we provide an overview of some of the existing change detection methods that utilize attribute information. We categorize these methods based on the levels of structure in the graph that are exploited to detect changes. These levels are vertices, edges, subgraphs, communities and the overall graph. We focus our attention on the strengths and weaknesses of these methods, including performance and scalability. Finally we discuss some publicly available dynamic network datasets and give a brief overview of simulation models to generate synthetic dynamic attributed networks.
Self-reciprocal and self-conjugate-reciprocal irreducible factors of $x^n-λ$ and their applications
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we present some necessary and sufficient conditions under which an irreducible polynomial is self-reciprocal (SR) or self-conjugate-reciprocal (SCR). By these characterizations, we obtain some enumeration formulas of SR and SCR irreducible factors of $x^n-λ$, $λ\in \Bbb F_q^*$, over $\Bbb F_q$, which are just open questions posed by Boripan {\em et al} (2019). We also count the numbers of Euclidean and Hermitian LCD constacyclic codes and show some well-known results on Euclidean and Hermitian self-dual constacyclic codes in a simple and direct way.
Neural Architecture Search for Deep Image Prior
Venue: arXiv cs.CV 2020
Year: 2020

We present a neural architecture search (NAS) technique to enhance the performance of unsupervised image de-noising, in-painting and super-resolution under the recently proposed Deep Image Prior (DIP). We show that evolutionary search can automatically optimize the encoder-decoder (E-D) structure and meta-parameters of the DIP network, which serves as a content-specific prior to regularize these single image restoration tasks. Our binary representation encodes the design space for an asymmetric E-D network that typically converges to yield a content-specific DIP within 10-20 generations using a population size of 500. The optimized architectures consistently improve upon the visual quality of classical DIP for a diverse range of photographic and artistic content.
Continuum modelling of stress diffusion interactions in an elastoplastic medium in the presence of geometric discontinuity
Venue: arXiv cs.CE 2020
Year: 2020

Chemo-mechanical coupled systems have been a subject of interest for many decades now. Previous attempts to solve such models have mainly focused on elastic materials without taking into account the plastic deformation beyond yield, thus causing inaccuracies in failure calculations. This paper aims to study the effect of stress-diffusion interactions in an elastoplastic material using a coupled chemo-mechanical system. The induced stress is dependent on the local concentration in a one way coupled system, and vice versa in a two way coupled system. The time-dependent transient coupled system is solved using a finite element formulation in an open-source finite element solver FEniCS. This paper attempts to computationally study the interaction of deformation and diffusion and its effect on the localization of plastic strain. We investigate the role of geometric discontinuities in scenarios involving diffusing species, namely, a plate with a notch/hole/void and particle with a void/hole/core. We also study the effect of stress concentrations and plastic yielding on the diffusion-deformation. The developed code can be from https://github.com/mrupeshkumar/Elastoplastic-stress-diffusion-coupling
Enabling the Analysis of Personality Aspects in Recommender Systems
Venue: arXiv cs.IR 2020
Year: 2020

Existing Recommender Systems mainly focus on exploiting users' feedback, e.g., ratings, and reviews on common items to detect similar users. Thus, they might fail when there are no common items of interest among users. We call this problem the Data Sparsity With no Feedback on Common Items (DSW-n-FCI). Personality-based recommender systems have shown a great success to identify similar users based on their personality types. However, there are only a few personality-based recommender systems in the literature which either discover personality explicitly through filling a questionnaire that is a tedious task, or neglect the impact of users' personal interests and level of knowledge, as a key factor to increase recommendations' acceptance. Differently, we identifying users' personality type implicitly with no burden on users and incorporate it along with users' personal interests and their level of knowledge. Experimental results on a real-world dataset demonstrate the effectiveness of our model, especially in DSW-n-FCI situations.
Fairness in Learning-Based Sequential Decision Algorithms: A Survey
Venue: arXiv cs.AI 2020
Year: 2020

Algorithmic fairness in decision-making has been studied extensively in static settings where one-shot decisions are made on tasks such as classification. However, in practice most decision-making processes are of a sequential nature, where decisions made in the past may have an impact on future data. This is particularly the case when decisions affect the individuals or users generating the data used for future decisions. In this survey, we review existing literature on the fairness of data-driven sequential decision-making. We will focus on two types of sequential decisions: (1) past decisions have no impact on the underlying user population and thus no impact on future data; (2) past decisions have an impact on the underlying user population and therefore the future data, which can then impact future decisions. In each case the impact of various fairness interventions on the underlying population is examined.
Physical-Virtual Collaboration Modeling for Intra-and Inter-Station Metro Ridership Prediction
Venue: arXiv cs.LG 2020
Year: 2020

Due to the widespread applications in real-world scenarios, metro ridership prediction is a crucial but challenging task in intelligent transportation systems. However, conventional methods either ignore the topological information of metro systems or directly learn on physical topology, and cannot fully explore the patterns of ridership evolution. To address this problem, we model a metro system as graphs with various topologies and propose a unified Physical-Virtual Collaboration Graph Network (PVCGN), which can effectively learn the complex ridership patterns from the tailor-designed graphs. Specifically, a physical graph is directly built based on the realistic topology of the studied metro system, while a similarity graph and a correlation graph are built with virtual topologies under the guidance of the inter-station passenger flow similarity and correlation. These complementary graphs are incorporated into a Graph Convolution Gated Recurrent Unit (GC-GRU) for spatial-temporal representation learning. Further, a Fully-Connected Gated Recurrent Unit (FC-GRU) is also applied to capture the global evolution tendency. Finally, we develop a Seq2Seq model with GC-GRU and FC-GRU to forecast the future metro ridership sequentially. Extensive experiments on two large-scale benchmarks (e.g., Shanghai Metro and Hangzhou Metro) well demonstrate the superiority of our PVCGN for station-level metro ridership prediction. Moreover, we apply the proposed PVCGN to address the online origin-destination (OD) ridership prediction and the experiment results show the universality of our method. Our code and benchmarks are available at https://github.com/HCPLab-SYSU/PVCGN.
Accurate iteration-free mixed-stabilised formulation for laminar incompressible Navier-Stokes: Applications to fluid-structure interaction
Venue: arXiv cs.CE 2020
Year: 2020

Stabilised mixed velocity-pressure formulations are one of the widely-used finite element schemes for computing the numerical solutions of laminar incompressible Navier-Stokes. In these formulations, the Newton-Raphson scheme is employed to solve the nonlinearity in the convection term. One fundamental issue with this approach is the computational cost incurred in the Newton-Raphson iterations at every load/time step. In this paper, we present an iteration-free mixed finite element formulation for incompressible Navier-Stokes that preserves second-order temporal accuracy of the generalised-alpha and related schemes for both velocity and pressure fields. First, we demonstrate the second-order temporal accuracy using numerical convergence studies for an example with a manufactured solution. Later, we assess the accuracy and the computational benefits of the proposed scheme by studying the benchmark example of flow past a fixed circular cylinder. Towards showcasing the applicability of the proposed technique in a wider context, the inf-sup stable P2-P1 pair for the formulation without stabilisation is also considered. Finally, the resulting benefits of using the proposed scheme for fluid-structure interaction problems is illustrated using two benchmark examples in fluid-flexible structure interaction.
Private Machine Learning via Randomised Response
Venue: arXiv cs.LG 2020
Year: 2020

We introduce a general learning framework for private machine learning based on randomised response. Our assumption is that all actors are potentially adversarial and as such we trust only to release a single noisy version of an individual's datapoint. We discuss a general approach that forms a consistent way to estimate the true underlying machine learning model and demonstrate this in the case of logistic regression.
The geometry of syntax and semantics for directed file transformations
Venue: arXiv cs.LO 2020
Year: 2020

We introduce a conceptual framework that associates syntax and semantics with vertical and horizontal directions in principal bundles and related constructions. This notion of geometry corresponds to a mechanism for performing goal-directed file transformations such as "eliminate unsafe syntax" and suggests various engineering practices.