OpenRaiser/Intern-Atlas huggingface dataset:
Comparison of Algorithms for Simple Stochastic Games
Venue: arXiv cs.GT 2020
Year: 2020

Simple stochastic games are turn-based 2.5-player zero-sum graph games with a reachability objective. The problem is to compute the winning probability as well as the optimal strategies of both players. In this paper, we compare the three known classes of algorithms -- value iteration, strategy iteration and quadratic programming -- both theoretically and practically. Further, we suggest several improvements for all algorithms, including the first approach based on quadratic programming that avoids transforming the stochastic game to a stopping one. Our extensive experiments show that these improvements can lead to significant speed-ups. We implemented all algorithms in PRISM-games 3.0, thereby providing the first implementation of quadratic programming for solving simple stochastic games.
Time-Optimal Self-Stabilizing Leader Election on Rings in Population Protocols
Venue: arXiv cs.DC 2020
Year: 2020

We propose a self-stabilizing leader election protocol on directed rings in the model of population protocols. Given an upper bound $N$ on the population size $n$, the proposed protocol elects a unique leader within $O(nN)$ expected steps starting from any configuration and uses $O(N)$ states. This convergence time is optimal if a given upper bound $N$ is asymptotically tight, i.e., $N=O(n)$.
Pose Imitation Constraints for Collaborative Robots
Venue: arXiv cs.RO 2020
Year: 2020

Achieving human-like motion in robots has been a fundamental goal in many areas of robotics research. Inverse kinematic (IK) solvers have been explored as a solution to provide kinematic structures with anthropomorphic movements. In particular, numeric solvers based on geometry, such as FABRIK, have shown potential for producing human-like motion at a low computational cost. Nevertheless, these methods have shown limitations when solving for robot kinematic constraints. This work proposes a framework inspired by FABRIK for human pose imitation in real-time. The goal is to mitigate the problems of the original algorithm while retaining the resulting humanlike fluidity and low cost. We first propose a human constraint model for pose imitation. Then, we present a pose imitation algorithm (PIC), and it's soft version (PICs) that can successfully imitate human poses using the proposed constraint system. PIC was tested on two collaborative robots (Baxter and YuMi). Fifty human demonstrations were collected for a bi-manual assembly and an incision task. Then, two performance metrics were obtained for both robots: pose accuracy with respect to the human and the percentage of environment occlusion/obstruction. The performance of PIC and PICs was compared against the numerical solver baseline (FABRIK). The proposed algorithms achieve a higher pose accuracy than FABRIK for both tasks (25%-FABRIK, 53%-PICs, 58%-PICs). In addition, PIC and it's soft version achieve a lower percentage of occlusion during incision (10%-FABRIK, 4%-PICs, 9%-PICs). These results indicate that the PIC method can reproduce human poses and achieve key desired effects of human imitation.
Towards a Flexible Embedding Learning Framework
Venue: arXiv cs.LG 2020
Year: 2020

Representation learning is a fundamental building block for analyzing entities in a database. While the existing embedding learning methods are effective in various data mining problems, their applicability is often limited because these methods have pre-determined assumptions on the type of semantics captured by the learned embeddings, and the assumptions may not well align with specific downstream tasks. In this work, we propose an embedding learning framework that 1) uses an input format that is agnostic to input data type, 2) is flexible in terms of the relationships that can be embedded into the learned representations, and 3) provides an intuitive pathway to incorporate domain knowledge into the embedding learning process. Our proposed framework utilizes a set of entity-relation-matrices as the input, which quantifies the affinities among different entities in the database. Moreover, a sampling mechanism is carefully designed to establish a direct connection between the input and the information captured by the output embeddings. To complete the representation learning toolbox, we also outline a simple yet effective post-processing technique to properly visualize the learned embeddings. Our empirical results demonstrate that the proposed framework, in conjunction with a set of relevant entity-relation-matrices, outperforms the existing state-of-the-art approaches in various data mining tasks.
Segmented Pairwise Distance for Time Series with Large Discontinuities
Venue: arXiv cs.DB 2020
Year: 2020

Time series with large discontinuities are common in many scenarios. However, existing distance-based algorithms (e.g., DTW and its derivative algorithms) may perform poorly in measuring distances between these time series pairs. In this paper, we propose the segmented pairwise distance (SPD) algorithm to measure distances between time series with large discontinuities. SPD is orthogonal to distance-based algorithms and can be embedded in them. We validate advantages of SPD-embedded algorithms over corresponding distance-based ones on both open datasets and a proprietary dataset of surgical time series (of surgeons performing a temporal bone surgery in a virtual reality surgery simulator). Experimental results demonstrate that SPD-embedded algorithms outperform corresponding distance-based ones in distance measurement between time series with large discontinuities, measured by the Silhouette index (SI).
Streamlining Cross-Document Coreference Resolution: Evaluation and Modeling
Venue: arXiv cs.CL 2020
Year: 2020

Recent evaluation protocols for Cross-document (CD) coreference resolution have often been inconsistent or lenient, leading to incomparable results across works and overestimation of performance. To facilitate proper future research on this task, our primary contribution is proposing a pragmatic evaluation methodology which assumes access to only raw text -- rather than assuming gold mentions, disregards singleton prediction, and addresses typical targeted settings in CD coreference resolution. Aiming to set baseline results for future research that would follow our evaluation methodology, we build the first end-to-end model for this task. Our model adapts and extends recent neural models for within-document coreference resolution to address the CD coreference setting, which outperforms state-of-the-art results by a significant margin.
Reliable, Fair and Decentralized Marketplace for Content Sharing Using Blockchain
Venue: arXiv cs.CR 2020
Year: 2020

Content sharing platforms such as Youtube and Vimeo have promoted pay per view models for artists to monetize their content. Yet, artists remain at the mercy of centralized platforms that control content listing and advertisement, with little transparency and fairness in terms of number of views or revenue. On the other hand, consumers are distanced from the publishers and cannot authenticate originality of the content. In this paper, we develop a reliable and fair platform for content sharing without a central facilitator. The platform is built as a decentralized data storage layer to store and share content in a fault-tolerant manner, where the peers also participate in a blockchain network. The blockchain is used to manage content listings and as an auditable and fair marketplace transaction processor that automatically pays out the content creators and the storage facilitators using smart contracts. We demonstrate the system with the blockchain layer built on Hyperledger Fabric and the data layer built on Tahoe-LAFS,and show that our design is practical and scalable with low overheads.
A Privacy-Preserving Protocol for the Kidney Exchange Problem
Venue: arXiv cs.CR 2020
Year: 2020

Kidney donations from living donors form an attractive alternative to long waiting times on a list for a post-mortem donation. However, even if a living donor for a given patient is found, the donor's kidney might not meet the patient's medical requirements. If several patients are in this position, they may be able to exchange donors in a cyclic fashion. Current algorithmic approaches for determining such exchange cycles neglect the privacy requirements of donors and patients as they require their medical data to be centrally collected and evaluated. In this paper, we present the first distributed privacy-preserving protocol for kidney exchange that ensures the correct computing of the exchange cycles while at the same time protecting the privacy of the patients' sensitive medical data. We prove correctness and security of the new protocol and evaluate its practical performance.
Text Classification with Novelty Detection
Venue: arXiv cs.LG 2020
Year: 2020

This paper studies the problem of detecting novel or unexpected instances in text classification. In traditional text classification, the classes appeared in testing must have been seen in training. However, in many applications, this is not the case because in testing, we may see unexpected instances that are not from any of the training classes. In this paper, we propose a significantly more effective approach that converts the original problem to a pair-wise matching problem and then outputs how probable two instances belong to the same class. Under this approach, we present two models. The more effective model uses two embedding matrices of a pair of instances as two channels of a CNN. The output probabilities from such pairs are used to judge whether a test instance is from a seen class or is novel/unexpected. Experimental results show that the proposed method substantially outperforms the state-of-the-art baselines.
A new evolutionary algorithm: Learner performance based behavior algorithm
Venue: arXiv cs.CY 2020
Year: 2020

A novel evolutionary algorithm called learner performance based behavior algorithm (LPB) is proposed in this article. The basic inspiration of LPB originates from the process of accepting graduated learners from high school in different departments at university. In addition, the changes those learners should do in their studying behaviors to improve their study level at university. The most important stages of optimization; exploitation and exploration are outlined by designing the process of accepting graduated learners from high school to university and the procedure of improving the learner's studying behavior at university to improve the level of their study. To show the accuracy of the proposed algorithm, it is evaluated against a number of test functions, such as traditional benchmark functions, CEC-C06 2019 test functions, and a real-world case study problem. The results of the proposed algorithm are then compared to the DA, GA, and PSO. The proposed algorithm produced superior results in most of the cases and comparative in some others. It is proved that the algorithm has a great ability to deal with the large optimization problems comparing to the DA, GA, and PSO. The overall results proved the ability of LPB in improving the initial population and converging towards the global optima. Moreover, the results of the proposed work are proved statistically.
Studying Person-Specific Pointing and Gaze Behavior for Multimodal Referencing of Outside Objects from a Moving Vehicle
Venue: arXiv cs.HC 2020
Year: 2020

Hand pointing and eye gaze have been extensively investigated in automotive applications for object selection and referencing. Despite significant advances, existing outside-the-vehicle referencing methods consider these modalities separately. Moreover, existing multimodal referencing methods focus on a static situation, whereas the situation in a moving vehicle is highly dynamic and subject to safety-critical constraints. In this paper, we investigate the specific characteristics of each modality and the interaction between them when used in the task of referencing outside objects (e.g. buildings) from the vehicle. We furthermore explore person-specific differences in this interaction by analyzing individuals' performance for pointing and gaze patterns, along with their effect on the driving task. Our statistical analysis shows significant differences in individual behaviour based on object's location (i.e. driver's right side vs. left side), object's surroundings, driving mode (i.e. autonomous vs. normal driving) as well as pointing and gaze duration, laying the foundation for a user-adaptive approach.
A Fleet Learning Architecture for Enhanced Behavior Predictions during Challenging External Conditions
Venue: arXiv cs.RO 2020
Year: 2020

Already today, driver assistance systems help to make daily traffic more comfortable and safer. However, there are still situations that are quite rare but are hard to handle at the same time. In order to cope with these situations and to bridge the gap towards fully automated driving, it becomes necessary to not only collect enormous amounts of data but rather the right ones. This data can be used to develop and validate the systems through machine learning and simulation pipelines. Along this line this paper presents a fleet learning-based architecture that enables continuous improvements of systems predicting the movement of surrounding traffic participants. Moreover, the presented architecture is applied to a testing vehicle in order to prove the fundamental feasibility of the system. Finally, it is shown that the system collects meaningful data which are helpful to improve the underlying prediction systems.
Randomized fast no-loss expert system to play tic tac toe like a human
Venue: arXiv cs.AI 2020
Year: 2020

This paper introduces a blazingly fast, no-loss expert system for Tic Tac Toe using Decision Trees called T3DT, that tries to emulate human gameplay as closely as possible. It does not make use of any brute force, minimax or evolutionary techniques, but is still always unbeatable. In order to make the gameplay more human-like, randomization is prioritized and T3DT randomly chooses one of the multiple optimal moves at each step. Since it does not need to analyse the complete game tree at any point, T3DT is exceptionally faster than any brute force or minimax algorithm, this has been shown theoretically as well as empirically from clock-time analyses in this paper. T3DT also doesn't need the data sets or the time to train an evolutionary model, making it a practical no-loss approach to play Tic Tac Toe.
A Comparative Study on Structural and Semantic Properties of Sentence Embeddings
Venue: arXiv cs.CL 2020
Year: 2020

Sentence embeddings encode natural language sentences as low-dimensional dense vectors. A great deal of effort has been put into using sentence embeddings to improve several important natural language processing tasks. Relation extraction is such an NLP task that aims at identifying structured relations defined in a knowledge base from unstructured text. A promising and more efficient approach would be to embed both the text and structured knowledge in low-dimensional spaces and discover semantic alignments or mappings between them. Although a number of techniques have been proposed in the literature for embedding both sentences and knowledge graphs, little is known about the structural and semantic properties of these embedding spaces in terms of relation extraction. In this paper, we investigate the aforementioned properties by evaluating the extent to which sentences carrying similar senses are embedded in close proximity sub-spaces, and if we can exploit that structure to align sentences to a knowledge graph. We propose a set of experiments using a widely-used large-scale data set for relation extraction and focusing on a set of key sentence embedding methods. We additionally provide the code for reproducing these experiments at https://github.com/akalino/semantic-structural-sentences. These embedding methods cover a wide variety of techniques ranging from simple word embedding combination to transformer-based BERT-style model. Our experimental results show that different embedding spaces have different degrees of strength for the structural and semantic properties. These results provide useful information for developing embedding-based relation extraction methods.
Interactive Learning for Semantic Segmentation in Earth Observation
Venue: arXiv cs.CV 2020
Year: 2020

Dense pixel-wise classification maps output by deep neural networks are of extreme importance for scene understanding. However, these maps are often partially inaccurate due to a variety of possible factors. Therefore, we propose to interactively refine them within a framework named DISCA (Deep Image Segmentation with Continual Adaptation). It consists of continually adapting a neural network to a target image using an interactive learning process with sparse user annotations as ground-truth. We show through experiments on three datasets using synthesized annotations the benefits of the approach, reaching an IoU improvement up to 4.7% for ten sampled clicks. Finally, we exhibit that our approach can be particularly rewarding when it is faced to additional issues such as domain adaptation.
Fuzzy Simplicial Networks: A Topology-Inspired Model to Improve Task Generalization in Few-shot Learning
Venue: arXiv cs.LG 2020
Year: 2020

Deep learning has shown great success in settings with massive amounts of data but has struggled when data is limited. Few-shot learning algorithms, which seek to address this limitation, are designed to generalize well to new tasks with limited data. Typically, models are evaluated on unseen classes and datasets that are defined by the same fundamental task as they are trained for (e.g. category membership). One can also ask how well a model can generalize to fundamentally different tasks within a fixed dataset (for example: moving from category membership to tasks that involve detecting object orientation or quantity). To formalize this kind of shift we define a notion of "independence of tasks" and identify three new sets of labels for established computer vision datasets that test a model's ability to generalize to tasks which draw on orthogonal attributes in the data. We use these datasets to investigate the failure modes of metric-based few-shot models. Based on our findings, we introduce a new few-shot model called Fuzzy Simplicial Networks (FSN) which leverages a construction from topology to more flexibly represent each class from limited data. In particular, FSN models can not only form multiple representations for a given class but can also begin to capture the low-dimensional structure which characterizes class manifolds in the encoded space of deep networks. We show that FSN outperforms state-of-the-art models on the challenging tasks we introduce in this paper while remaining competitive on standard few-shot benchmarks.
An Embedded Index Code Construction Using Sub-packetization
Venue: arXiv cs.IT 2020
Year: 2020

A variant of the index coding problem (ICP), the embedded index coding problem (EICP) was introduced in [A. Porter and M. Wootters, "Embedded index coding," ITW, Sweden, 2019] which was motivated by its application in distributed computing where every user can act as sender for other users and an algorithm for code construction was reported. The constructions depends on the computation of minrank of a matrix, which is computationally intensive. In [A. Mahesh, N. Sageer Karat and B. S. Rajan, "Min-rank of Embedded Index Coding Problems," ISIT, 2020], for EICP, a notion of side-information matrix was introduced and it was proved that the length of an optimal scalar linear index code is equal to the min-rank of the side-information matrix. The authors have provided an explicit code construction for a class of EICP - \textit{Consecutive and Symmetric Embedded Index Coding Problem (CS-EICP)}. We introduce the idea of sub-packetization of the messages in index coding problems to provide a novel code construction for CS-EICP in contrast to the scalar linear solutions provided in the prior works. For CS-EICP, the normalized rate, which is defined as the number of bits transmitted by all the users together normalized by the total number of bits of all the messages, for our construction is lesser than the normalized rate achieved by Mahesh et al.,for scalar linear codes.
Dataset Optimization Strategies for MalwareTraffic Detection
Venue: arXiv cs.LG 2020
Year: 2020

Machine learning is rapidly becoming one of the most important technology for malware traffic detection, since the continuous evolution of malware requires a constant adaptation and the ability to generalize. However, network traffic datasets are usually oversized and contain redundant and irrelevant information, and this may dramatically increase the computational cost and decrease the accuracy of most classifiers, with the risk to introduce further noise. We propose two novel dataset optimization strategies which exploit and combine several state-of-the-art approaches in order to achieve an effective optimization of the network traffic datasets used to train malware detectors. The first approach is a feature selection technique based on mutual information measures and sensibility enhancement. The second is a dimensional reduction technique based autoencoders. Both these approaches have been experimentally applied on the MTA-KDD'19 dataset, and the optimized results evaluated and compared using a Multi Layer Perceptron as machine learning model for malware detection.
An Online and Nonuniform Timeslicing Method for Network Visualisation
Venue: arXiv cs.SI 2020
Year: 2020

Visual analysis of temporal networks comprises an effective way to understand the network dynamics, facilitating the identification of patterns, anomalies, and other network properties, thus resulting in fast decision making. The amount of data in real-world networks, however, may result in a layout with high visual clutter due to edge overlapping. This is particularly relevant in the so-called streaming networks, in which edges are continuously arriving (online) and in non-stationary distribution. All three network dimensions, namely node, edge, and time, can be manipulated to reduce such clutter and improve readability. This paper presents an online and nonuniform timeslicing method, thus considering the underlying network structure and addressing streaming network analyses. We conducted experiments using two real-world networks to compare our method against uniform and nonuniform timeslicing strategies. The results show that our method automatically selects timeslices that effectively reduce visual clutter in periods with bursts of events. As a consequence, decision making based on the identification of global temporal patterns becomes faster and more reliable.