OpenRaiser/Intern-Atlas huggingface dataset:
Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss
Venue: arXiv cs.DS 2020
Year: 2020

We study the column subset selection problem with respect to the entrywise $\ell_1$-norm loss. It is known that in the worst case, to obtain a good rank-$k$ approximation to a matrix, one needs an arbitrarily large $n^{Ω(1)}$ number of columns to obtain a $(1+ε)$-approximation to the best entrywise $\ell_1$-norm low rank approximation of an $n \times n$ matrix. Nevertheless, we show that under certain minimal and realistic distributional settings, it is possible to obtain a $(1+ε)$-approximation with a nearly linear running time and poly$(k/ε)+O(k\log n)$ columns. Namely, we show that if the input matrix $A$ has the form $A = B + E$, where $B$ is an arbitrary rank-$k$ matrix, and $E$ is a matrix with i.i.d. entries drawn from any distribution $μ$ for which the $(1+γ)$-th moment exists, for an arbitrarily small constant $γ> 0$, then it is possible to obtain a $(1+ε)$-approximate column subset selection to the entrywise $\ell_1$-norm in nearly linear time. Conversely we show that if the first moment does not exist, then it is not possible to obtain a $(1+ε)$-approximate subset selection algorithm even if one chooses any $n^{o(1)}$ columns. This is the first algorithm of any kind for achieving a $(1+ε)$-approximation for entrywise $\ell_1$-norm loss low rank approximation.
An Exploration of IoT Platform Development
Venue: arXiv cs.SE 2020
Year: 2020

Internet of Things platforms are key enablers for smart city initiatives, targeting the improvement of citizens quality of life and economic growth. As IoT platforms are dynamic, proactive, and heterogeneous socio-technical artefacts, systematic approaches are required for their development. Limited surveys have exclusively explored how IoT platforms are developed and maintained from the perspective of information system development process lifecycle. In this paper, we present a detailed analysis of 63 approaches. This is accomplished by proposing an evaluation framework as a cornerstone to highlight the characteristics, strengths, and weaknesses of these approaches. The survey results not only provide insights of empirical findings, recommendations, and mechanisms for the development of quality aware IoT platforms, but also identify important issues and gaps that need to be addressed.
A study of influential factors in designing self-reconfigurable robots for green manufacturing
Venue: arXiv cs.RO 2020
Year: 2020

There is incremental growth in adopting self-reconfigurable robots in automating manufacturing conventional product lines. Using this class of robots adapting themselves with ever-changing environmental conditions has been acclaimed as a promising way of reducing energy consumption and environmental impact and thus enabling green manufacturing. Whilst the majority of existing research focuses on highlighting the efficacy of self-reconfigurable robots in energy reduction with technical driven solutions, the research on exploring the salient factors in design and development self-reconfigurable robots that directly enable or hinder green manufacturing is non-extant. This interdisciplinary research contributes to the nascent body of the knowledge by empirical investigation of design-time, run-time, and hardware aspects which should be contingently balanced when developing green-aware self-reconfigurable robots. Keywords Green manufacturing, self-reconfigurable robots, robot design, green awareness
Computation Offloading in Heterogeneous Mobile Edge Computing with Energy Harvesting
Venue: arXiv cs.IT 2020
Year: 2020

Energy harvesting aided mobile edge computing (MEC) has gained much attention for its widespread application in the computation-intensive, latency-sensitive and energy-hungry scenario. In this paper, computation offloading from multi-MD to multi-MEC-s in heterogeneous MEC systems with energy harvesting is investigated from a game theoretic perspective. The objective is to minimize the average response time of an MD that consists of communication time, waiting time and processing time. M/G/1 queueing models are established for MDs and MEC-ss. The interference among MDs, the randomness in computation task generation, harvested energy arrival, wireless channel state, queueing at the MEC-s, and the power budget constraint of an MD are taken into consideration. A noncooperative computation offloading game is formulated. We give the definition and existence analysis of the Nash equilibrium (NE). Furthermore, we reconstruct the optimization problem of an MD. A 2-step decomposition is presented and performed. Thereby, we arrive at a one-dimensional search problem and a greatly shrunken sub-problem. We can obtain the optimal solution of the sub-problem by seeking the finite solutions of its Karush-Kuhn-Tucker (KKT) conditions. Thereafter, a distributive NE-orienting iterated best-response algorithm is designed. Simulations are carried out to illustrate the convergence performance and parameter effect.
Batch Clustering for Multilingual News Streaming
Venue: arXiv cs.CL 2020
Year: 2020

Nowadays, digital news articles are widely available, published by various editors and often written in different languages. This large volume of diverse and unorganized information makes human reading very difficult or almost impossible. This leads to a need for algorithms able to arrange high amount of multilingual news into stories. To this purpose, we extend previous works on Topic Detection and Tracking, and propose a new system inspired from newsLens. We process articles per batch, looking for monolingual local topics which are then linked across time and languages. Here, we introduce a novel "replaying" strategy to link monolingual local topics into stories. Besides, we propose new fine tuned multilingual embedding using SBERT to create crosslingual stories. Our system gives monolingual state-of-the-art results on dataset of Spanish and German news and crosslingual state-of-the-art results on English, Spanish and German news.
NAIST COVID: Multilingual COVID-19 Twitter and Weibo Dataset
Venue: arXiv cs.SI 2020
Year: 2020

Since the outbreak of coronavirus disease 2019 (COVID-19) in the late 2019, it has affected over 200 countries and billions of people worldwide. This has affected the social life of people owing to enforcements, such as "social distancing" and "stay at home." This has resulted in an increasing interaction through social media. Given that social media can bring us valuable information about COVID-19 at a global scale, it is important to share the data and encourage social media studies against COVID-19 or other infectious diseases. Therefore, we have released a multilingual dataset of social media posts related to COVID-19, consisting of microblogs in English and Japanese from Twitter and those in Chinese from Weibo. The data cover microblogs from January 20, 2020, to March 24, 2020. This paper also provides a quantitative as well as qualitative analysis of these datasets by creating daily word clouds as an example of text-mining analysis. The dataset is now available on Github. This dataset can be analyzed in a multitude of ways and is expected to help in efficient communication of precautions related to COVID-19.
Continuous Representation of Molecules Using Graph Variational Autoencoder
Venue: arXiv cs.LG 2020
Year: 2020

In order to continuously represent molecules, we propose a generative model in the form of a VAE which is operating on the 2D-graph structure of molecules. A side predictor is employed to prune the latent space and help the decoder in generating meaningful adjacency tensor of molecules. Other than the potential applicability in drug design and property prediction, we show the superior performance of this technique in comparison to other similar methods based on the SMILES representation of the molecules with RNN based encoder and decoder.
Hilbert geometry of the Siegel disk: The Siegel-Klein disk model
Venue: arXiv cs.CG 2020
Year: 2020

We study the Hilbert geometry induced by the Siegel disk domain, an open bounded convex set of complex square matrices of operator norm strictly less than one. This Hilbert geometry yields a generalization of the Klein disk model of hyperbolic geometry, henceforth called the Siegel-Klein disk model to differentiate it with the classical Siegel upper plane and disk domains. In the Siegel-Klein disk, geodesics are by construction always unique and Euclidean straight, allowing one to design efficient geometric algorithms and data-structures from computational geometry. For example, we show how to approximate the smallest enclosing ball of a set of complex square matrices in the Siegel disk domains: We compare two generalizations of the iterative core-set algorithm of Badoiu and Clarkson (BC) in the Siegel-Poincaré disk and in the Siegel-Klein disk: We demonstrate that geometric computing in the Siegel-Klein disk allows one (i) to bypass the time-costly recentering operations to the disk origin required at each iteration of the BC algorithm in the Siegel-Poincaré disk model, and (ii) to approximate fast and numerically the Siegel-Klein distance with guaranteed lower and upper bounds derived from nested Hilbert geometries.
Finding the Optimal Network Depth in Classification Tasks
Venue: arXiv cs.LG 2020
Year: 2020

We develop a fast end-to-end method for training lightweight neural networks using multiple classifier heads. By allowing the model to determine the importance of each head and rewarding the choice of a single shallow classifier, we are able to detect and remove unneeded components of the network. This operation, which can be seen as finding the optimal depth of the model, significantly reduces the number of parameters and accelerates inference across different hardware processing units, which is not the case for many standard pruning methods. We show the performance of our method on multiple network architectures and datasets, analyze its optimization properties, and conduct ablation studies.
An Annotated Dataset of Stack Overflow Post Edits
Venue: arXiv cs.SE 2020
Year: 2020

To improve software engineering, software repositories have been mined for code snippets and bug fixes. Typically, this mining takes place at the level of files or commits. To be able to dig deeper and to extract insights at a higher resolution, we hereby present an annotated dataset that contains over 7 million edits of code and text on Stack Overflow. Our preliminary study indicates that these edits might be a treasure trove for mining information about fine-grained patches, e.g., for the optimisation of non-functional properties.
Learning-Based Joint User-AP Association and Resource Allocation in Ultra Dense Network
Venue: arXiv cs.NI 2020
Year: 2020

With the advantages of Millimeter wave in wireless communication network, the coverage radius and inter-site distance can be further reduced, the ultra dense network (UDN) becomes the mainstream of future networks. The main challenge faced by UDN is the serious inter-site interference, which needs to be carefully addressed by joint user association and resource allocation methods. In this paper, we propose a multi-agent Q-learning based method to jointly optimize the user association and resource allocation in UDN. The deep Q-network is applied to guarantee the convergence of the proposed method. Simulation results reveal the effectiveness of the proposed method and different performances under different simulation parameters are evaluated.
MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models
Venue: arXiv cs.LG 2020
Year: 2020

Dense, discrete Graphical Models with pairwise potentials are a powerful class of models which are employed in state-of-the-art computer vision and bio-imaging applications. This work introduces a new MAP-solver, based on the popular Dual Block-Coordinate Ascent principle. Surprisingly, by making a small change to the low-performing solver, the Max Product Linear Programming (MPLP) algorithm, we derive the new solver MPLP++ that significantly outperforms all existing solvers by a large margin, including the state-of-the-art solver Tree-Reweighted Sequential (TRWS) message-passing algorithm. Additionally, our solver is highly parallel, in contrast to TRWS, which gives a further boost in performance with the proposed GPU and multi-thread CPU implementations. We verify the superiority of our algorithm on dense problems from publicly available benchmarks, as well, as a new benchmark for 6D Object Pose estimation. We also provide an ablation study with respect to graph density.
Duplication Detection in Knowledge Graphs: Literature and Tools
Venue: arXiv cs.DB 2020
Year: 2020

In recent years, an increasing amount of knowledge graphs (KGs) have been created as a means to store cross-domain knowledge and billion of facts, which are the basis of costumers' applications like search engines. However, KGs inevitably have inconsistencies such as duplicates that might generate conflicting property values. Duplication detection (DD) aims to identify duplicated entities and resolve their conflicting property values effectively and efficiently. In this paper, we perform a literature review on DD methods and tools, and an evaluation of them. Our main contributions are a performance evaluation of DD tools in KGs, improvement suggestions, and a DD workflow to support future development of DD tools, which are based on desirable features detected through this study.
An Asynchronous Computability Theorem for Fair Adversaries
Venue: arXiv cs.DC 2020
Year: 2020

This paper proposes a simple topological characterization of a large class of fair adversarial models via affine tasks: sub-complexes of the second iteration of the standard chromatic subdivision. We show that the task computability of a model in the class is precisely captured by iterations of the corresponding affine task. Fair adversaries include, but are not restricted to, the models of wait-freedom, t-resilience, and $k$-concurrency. Our results generalize and improve all previously derived topological characterizations of the ability of a model to solve distributed tasks.
Robotic Room Traversal using Optical Range Finding
Venue: arXiv cs.RO 2020
Year: 2020

Consider the goal of visiting every part of a room that is not blocked by obstacles. Doing so efficiently requires both sensors and planning. Our findings suggest a method of inexpensive optical range finding for robotic room traversal. Our room traversal algorithm relies upon the approximate distance from the robot to the nearest obstacle in 360 degrees. We then choose the path with the furthest approximate distance. Since millimeter-precision is not required for our problem, we have opted to develop our own laser range finding solution, in lieu of using more common, but also expensive solutions like light detection and ranging (LIDAR). Rather, our solution uses a laser that casts a visible dot on the target and a common camera (an iPhone, for example). Based upon where in the camera frame the laser dot is detected, we may calculate an angle between our target and the laser aperture. Using this angle and the known distance between the camera eye and the laser aperture, we may solve all sides of a trigonometric model which provides the distance between the robot and the target.
Exploring the Combination of Contextual Word Embeddings and Knowledge Graph Embeddings
Venue: arXiv cs.CL 2020
Year: 2020

``Classical'' word embeddings, such as Word2Vec, have been shown to capture the semantics of words based on their distributional properties. However, their ability to represent the different meanings that a word may have is limited. Such approaches also do not explicitly encode relations between entities, as denoted by words. Embeddings of knowledge bases (KB) capture the explicit relations between entities denoted by words, but are not able to directly capture the syntagmatic properties of these words. To our knowledge, recent research have focused on representation learning that augment the strengths of one with the other. In this work, we begin exploring another approach using contextual and KB embeddings jointly at the same level and propose two tasks -- an entity typing and a relation typing task -- that evaluate the performance of contextual and KB embeddings. We also evaluated a concatenated model of contextual and KB embeddings with these two tasks, and obtain conclusive results on the first task. We hope our work may contribute as a basis for models and datasets that develop in the direction of this approach.
Deep Reinforcement Learning for Adaptive Learning Systems
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, we formulate the adaptive learning problem---the problem of how to find an individualized learning plan (called policy) that chooses the most appropriate learning materials based on learner's latent traits---faced in adaptive learning systems as a Markov decision process (MDP). We assume latent traits to be continuous with an unknown transition model. We apply a model-free deep reinforcement learning algorithm---the deep Q-learning algorithm---that can effectively find the optimal learning policy from data on learners' learning process without knowing the actual transition model of the learners' continuous latent traits. To efficiently utilize available data, we also develop a transition model estimator that emulates the learner's learning process using neural networks. The transition model estimator can be used in the deep Q-learning algorithm so that it can more efficiently discover the optimal learning policy for a learner. Numerical simulation studies verify that the proposed algorithm is very efficient in finding a good learning policy, especially with the aid of a transition model estimator, it can find the optimal learning policy after training using a small number of learners.
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary
Venue: arXiv cs.DS 2020
Year: 2020

Designing dynamic graph algorithms against an adaptive adversary is a major goal in the field of dynamic graph algorithms. While a few such algorithms are known for spanning trees, matchings, and single-source shortest paths, very little was known for an important primitive like graph sparsifiers. The challenge is how to approximately preserve so much information about the graph (e.g., all-pairs distances and all cuts) without revealing the algorithms' underlying randomness to the adaptive adversary. In this paper we present the first non-trivial efficient adaptive algorithms for maintaining spanners and cut sparisifers. These algorithms in turn imply improvements over existing algorithms for other problems. Our first algorithm maintains a polylog$(n)$-spanner of size $\tilde O(n)$ in polylog$(n)$ amortized update time. The second algorithm maintains an $O(k)$-approximate cut sparsifier of size $\tilde O(n)$ in $\tilde O(n^{1/k})$ amortized update time, for any $k\ge1$, which is polylog$(n)$ time when $k=\log(n)$. The third algorithm maintains a polylog$(n)$-approximate spectral sparsifier in polylog$(n)$ amortized update time. The amortized update time of both algorithms can be made worst-case by paying some sub-polynomial factors. Prior to our result, there were near-optimal algorithms against oblivious adversaries (e.g. Baswana et al. [TALG'12] and Abraham et al. [FOCS'16]), but the only non-trivial adaptive dynamic algorithm requires $O(n)$ amortized update time to maintain $3$- and $5$-spanner of size $O(n^{1+1/2})$ and $O(n^{1+1/3})$, respectively [Ausiello et al. ESA'05]. Our results are based on two novel techniques. The first technique, is a generic black-box reduction that allows us to assume that the graph undergoes only edge deletions and, more importantly, remains an expander with almost-uniform degree. The second technique we call proactive resampling. [...]
Adversarial Attack on Deep Learning-Based Splice Localization
Venue: arXiv cs.CV 2020
Year: 2020

Regarding image forensics, researchers have proposed various approaches to detect and/or localize manipulations, such as splices. Recent best performing image-forensics algorithms greatly benefit from the application of deep learning, but such tools can be vulnerable to adversarial attacks. Due to the fact that most of the proposed adversarial example generation techniques can be used only on end-to-end classifiers, the adversarial robustness of image-forensics methods that utilize deep learning only for feature extraction has not been studied yet. Using a novel algorithm capable of directly adjusting the underlying representations of patches we demonstrate on three non end-to-end deep learning-based splice localization tools that hiding manipulations of images is feasible via adversarial attacks. While the tested image-forensics methods, EXIF-SC, SpliceRadar, and Noiseprint, rely on feature extractors that were trained on different surrogate tasks, we find that the formed adversarial perturbations can be transferable among them regarding the deterioration of their localization performance.
Reducing Commutativity Verification to Reachability with Differencing Abstractions
Venue: arXiv cs.PL 2020
Year: 2020

Commutativity of data structure methods is of ongoing interest, with roots in the database community. In recent years commutativity has been shown to be a key ingredient to enabling multicore concurrency in contexts such as parallelizing compilers, transactional memory, speculative execution and, more broadly, software scalability. Despite this interest, it remains an open question as to how a data structure's commutativity specification can be verified automatically from its implementation. In this paper, we describe techniques to automatically prove the correctness of method commutativity conditions from data structure implementations. We introduce a new kind of abstraction that characterizes the ways in which the effects of two methods differ depending on the order in which the methods are applied, and abstracts away effects of methods that would be the same regardless of the order. We then describe a novel algorithm that reduces the problem to reachability, so that off-the-shelf program analysis tools can perform the reasoning necessary for proving commutativity. Finally, we describe a proof-of-concept implementation and experimental results, showing that our tool can verify commutativity of data structures such as a memory cell, counter, two-place Set, array-based stack, queue, and a rudimentary hash table. We conclude with a discussion of what makes a data structure's commutativity provable with today's tools and what needs to be done to prove more in the future.
A Subterranean Virtual Cave World for Gazebo based on the DARPA SubT Challenge
Venue: arXiv cs.RO 2020
Year: 2020

Subterranean environments with lots of obstacles, including narrow passages, large voids, rock falls and absence of illumination were always challenging for control, navigation, and perception of mobile robots. The limited availability and access to such environments restricts the development pace of capabilities for robotic platforms to autonomously accomplish tasks in such challenging areas. The Subterranean Challenge is a competition focusing on bringing robotic exploration a step closer to real life applications for man-made underground tunnels, urban areas and natural cave networks, envisioning advanced assistance tools for first responders and disaster relief agencies. The challenge offers a software-based virtual part to showcase technologies in autonomy perception, networking and mobility for such areas. Thus, the presented open-source virtual world aims to become a test-bed for evaluating the developed algorithms and software and to foster mobile robotics developments.